Chapter3. List-Stack-Queue

[TOC]

线性表和非线性表

线性表:顺序表/链表/栈/队列

非线性表:二叉树/图

线性表和非线性表的划分,是根据其逻辑来划分的,而不是根据其存储结构来划分的。每个线性表上的数据最多只有前后两个方向。

List

List 的分类

  • ArrayList: 顺序表

  • LinkList: 链表

顺序表和链表的区别

最本质的区别:顺序表在内存是连续存储的,而链表在内存中是离散存储的。

顺序表:连续存储 —> 索引,顺序表要根据索引进行查找

链表:离散存储 —> 指针,链表要根据指针进行查找

其他所有的区别,都源于这个最本质的区别,由于顺序表是连续存储的,所以可以根据索引进行快速查找,但是如果想要插入和删除,为了保持顺序表的连续性,部分元素就需要移位,而这正是链表所擅长的,链表的离散存储特性决定了其无法快速的查找,但是可以快速的进行插入/删除操作。

链表由于其需要另外开辟空间存储下一个节点的指针,所以其比顺序表要耗费更多的内存。并且由于链表的空间是离散分配的,在内存回收后,会产生更多的内存碎片,不方便利用。

线性表的使用场景更多一些,其相较于链表,更节省内存,而且可以借助 CPU 的缓存机制,加速线性表的访问速度。但是其缺点也很明显,其需要占用连续的存储空间,一旦申请的空间很大,就会导致申请失败;另外,如果申请的空间不够用,那么就得向操作系统申请一个更大的连续空间,然后将顺序表中的内容 copy 过去,而 copy 的操作是非常耗时的。

顺序表刷题总结

  • 顺序表的最大特点是其内存空间是连续的,可以通过 index 进行快速查找,所以顺序表的最大特点

用链表实现 LRU 算法

LRU(Least recently used) 算法需要频繁的插入删除,所以不适合用顺序表,可以使用链表来实现。

  1. 插入:头插法

  2. 查找:从头开始查找,查找到后将节点移到头节点后

  3. 删除:cache 满后,删除链尾

如何判断两个链表相交

$O(n^2)$: 两层遍历,总能发现是否相交

$O(n)$: 一层遍历,遍历完两个链表,如果两个链表的最后一个结点指针相同,则相交,否则不相交

Stack

栈的特点:先进后出

链式栈

链式栈

链式栈的优点:不存在栈满上溢的情况。

用栈实现队列

两个栈实现队列:

两个栈实现队列

队列的四个基本操作:

  • 入队

    入栈 1,栈 1 满后,如果栈 2 为空,则栈 1 内元素全部入栈 2,如果栈 2 不为空,则队满

  • 出队

    栈 2 出队,如果栈 2 为空,则栈 1 元素全部入栈 2,如果栈 1 也为空,则队列为空

  • 判断队列是否为空

    如果栈 1 和栈 2 都为空,则队列为空

用两个栈实现队列,代码实现:

后缀表达式,表达式求值

后缀表达式,表达式求值用到了栈,但是为什么要用到栈呢?栈的先进后出的思想到底体现在什么地方呢?

对于一个表达式,例如 $2 + 4 * 5$,这个问题到底哪里有栈的特点?细细品位,我们会发现,先进来的数 2 和操作符 + 并没有先参与运算,反而是后进来的 4 和 5 先进行了运算,这里就有用到栈的地方。

Leetcode: 150,

汉诺塔问题(hannoi)

Queue

用顺序表实现 Queue

顺序表实现 Queue 的关键在于:队首的索引 < 队尾的索引

顺序表实现 Queue