栈和队列学习笔记

淡淡的烟草味﹌ 2022-07-13 11:41 191阅读 0赞

栈和队列的比较简单，两种就是一个做了某些特殊限制的线性表。比如，去除线性表中可以通过通过索引访问元素的功能。去除通过某个元素得到索引位置的功能。去除普通线性表中可以在任意位置增删的功能，而只允许在线性表的某端进行，这样线性表就变成了特殊的线性表:栈，队列。

从逻辑上看。栈和队列其实是有普通线性表发展而来，普通线性表增加一些特殊的限制就可以得到栈和队列了。  
从功能上来看，栈和队列比普通线性表功能相对弱一些，但在一些特殊的场合下使用它们很有必要，比如编译器实现函数调用的时候就需要使用栈来存储断点，实现递归算法时需要栈来存储。

**栈的基本定义**  
栈代表只能在某一端进行插入，删除的特殊线性表，通常就是在线性表的尾端进行插入删除。  
对于线性表而言，允许进行插入，删除的一端被称为栈顶(top)，另一端被称为栈底(buttom)。

从top进入一个元素叫压栈push。  
从top删除一个元素叫弹栈pop。

如果a0，a1,a2….an依次push。那么pop的顺序为an，an-1，，，a0.你可以把栈想成一个玩具手枪的弹夹，先压进去的最后一个出来。这样特性我们称为FILO(先进后出)。

#### 栈的顺序存储: ####

顺序存储结构的栈简称顺序栈，它利用一组地址连续存储单元依次存放从top到bottom的数据元素。bottom的位置固定不变，它的top元素可以直接通过顺序栈底层数组的数组元素array\[size-1\]来访问。  
顺序栈中数据元素的物理关系和逻辑关系是一致的。

#### 栈的链式存储: ####

去可以采用单链表来保存栈中的所有元素，这种链式结构的栈也被称为链栈。对于链栈，栈顶元素不断的改变，程序只需要一个top引用来记录当前栈顶元素即可。top永远引用栈顶元素。然后再使用一个size变量记录当前栈中包含多少元素即可。

**由于不需要实现随机存取的功能，它只需要从在顶插入删除和元素，因此顺序结构的栈提供的高效存取就没有太大的价值。即使采用链式结构的实现程序同样也可以实现高效的push和pop。**

对于链栈而言，栈内有几个元素，底层链式结构就只需要保存几个节点。每个节点只需要额外再添加一个next的应用，这会增加部分空间的浪费。但对于顺序表的栈而言，程序最开始就需要在底层为它开辟一块连续的内存(数组)，这种空间浪费其实更大。从空间利用率角度来看，链栈的空间利用率比顺序表的空间利用率更高。

Java集合中的栈

java.util.Stack 普通的顺序栈，底层是数组。它是线程安全的。  
备注:Stack继承Vector。Vector是List接口的一个实现类。

java.util.LinkedList 虽然是个双向链表，但提供了push()，pop() , peek()等方法。所有它可以当成栈来使用，它不是线程安全的。

**队列**  
队列被固定的一段来插入数据元素，另一端只能用于删除元素。只允许在表的前端(front)进行删除操作，只允许在表的后端(rear)进行插入操作。就类似于排队购物一样，先进入队伍的顾客先获得服务。队列中元素的移动方向是固定的。进行插入操作的端称为队尾，进行删除操作的称为队头。

对于队列而言，数据总是从后端进入队列，而从前端被删除。因此，队列先进先出(FIFO)的线性表。

#### 队列的顺序存储: ####

系统采用一组地址连续的存储单元依次存放从rear端到front端的所有数据元素，程序只需front和rear两个整形变量来记录队列front端的元素索引，rear端的索引。

front总是保存着队列即将出队列的元素的索引。  
rear总是保存着队列即将进入队列的元素的索引。  
队列中元素的个数为rear-front。

对于顺序队列而言，队列底层将采用数组来保存队列元素，每个队列元素在数组中的位置是固定不变的，变得只是两个整型变量。当有元素进入队列时，rear变量的值+1。当有元素从队列中删除，front变量的值-1。

**队列的假满**  
![这里写图片描述][SouthEast]

对于上图的操作，当处于图二时，队列是真的满了。而当移除了所有的元素之后，图三，此时rear等于capacity，则程序无法继续添加元素来，而队列明明是空的。这就是假满。

假满地解决方法:  
1）每次将元素移除队列时都将程序中的所有元素向front移动一位，这种方式下front的值永远为0。元素插入队列时，rear值+1。元素移除队列时rear值-1。但这种方式非常浪费时间，因为每次都将元素从队列移除都需要整体搬家。

2)将数组存储区看成一个首尾相接的环形区域，当存放到数组的最大地址之后。rear的值再次变为0，采用这种存储技巧的队列称为循环队列。

**循环队列**  
为了充分利用顺序队列的底层数组中已删除的元素占用的空间，消除可能出现的”假满”现象，可以将顺序队列改进为循环队列。  
![这里写图片描述][SouthEast 1]  
循环队列就是首位相接的队列。当front，rear变为capacity-1的时候，再前进就变为0.参考上图理解。  
这样无论队列是空还是满，都会出现front===rear。底层数组如果elementDate\[front\]==null表明队列此时为空，否则队列为满。

**队列的链式存储结构**

类似于使用链式结构来保存线性表，也可以采用链式结构来存储队列中的元素，采用链式存储结构的队列也被称为链队列。

对于链队列而言，由于程序需要从rear端添加元素，然后从front端移除元素，因此考虑对链队列增加rear，front两个引用变量，使它们分别指向链队列的头,尾两个节点，链队列的结构如下图所示。

![这里写图片描述][SouthEast 2]

#### Java集合中的队列 ####

JDK1.5开启，java集合框架提供了一个Queue接口，该接口代表一个队列。实现该接口的类可以当成队列使用。Queue接口包含6个方法，用于代表队列所包含的3个标准性方法,如下图所示:  
**插入: 队列的rear端插入**  
**移除: 队列的front端移除**  
**访问:访问队列的front端元素**  
Java为上面的每个方法都提供了两个版本:**返回特殊的版本和抛出异常版本**，就产生了六个方法。

![这里写图片描述][SouthEast 3]

Java为Queue这个接口提供了一堆强大的实现类:

>  *  ArrayBlockingQueue ：一个由数组结构组成的有界阻塞队列。线程安全　顺序存储
>  *  LinkedBlockingQueue ：一个由链表结构组成的有界阻塞队列。线程安全　链式存储
>  *  PriorityBlockingQueue ：一个支持优先级排序的无界阻塞队列。
>  *  DelayQueue：一个使用优先级队列实现的无界阻塞队列。
>  *  SynchronousQueue：一个不存储元素的阻塞队列。
>  *  LinkedTransferQueue：一个由链表结构组成的无界阻塞队列。

ArrayBlockingQueue和LinkedBlockingQueue一个代表顺序存储，一个代表链式存储。两个都是线性安全的。不能看出，LinkedBlockingQueue队列吞吐量比ArrayBlockingQueue高。但在大多数并发应用程序中，LinkedBlockingQueue性能低。

除了上述之外，JDK还有另外一种链队列。ConcurrentLinkedQueue，它是基于一种先进的，无等待(wait-free)队列算法实现。  
JDK1。5还为Queue接口提供一个Deque接口，代表双向队列。

#### 双向队列 ####

双向队列(Deque)代表一种特殊的队列。它可以在两端同时进行插入，删除等操作。如果程序将双向队列的操作只固定在某一端进行，那么它就是栈。

![这里写图片描述][SouthEast 4]

上图表明三者的关系。  
不难看出，双向队列Deque即可以当成队列也可以当栈来使用。  
其实Deque其实是Queue和Stack混合成的特殊线性表。JDK虽然提供了古老是Stack接口，但并不推荐使用，而推荐将Deque当成Stack来使用。  
JDK为Deque接口提供了ArrayDeque，LinkedBlockingDeque，LinkedList三个实现类。**ArrayDeque代表顺序存储的双向队列，LinkedList代表线性安全的链式存储双向队列，而LinkedBlockingDeque代表线程安全的链式结构的队列。**

#### LinkedList ####

LinkedList代表一种双向，链式存储结构的循环线性表，也是一种线性安全，链式的双向队列。它是Java集合方法最多的一个类。

JDK提供的线性表，队列，栈关系类图：如下所示：

![这里写图片描述][SouthEast 5]

备注：虽然LinkedList功能强大。即是栈也是队列，但大部分情况下，ArrayList，ArrayDeque性能优于LinkedList。

[SouthEast]: /images/20220713/8352df1a0c6347d2bdba7509d5dce74b.png
[SouthEast 1]: /images/20220713/36d4212e80c7408495308cd9aeb17ae7.png
[SouthEast 2]: /images/20220713/ab51f82bb1ff407fa511cebcde30ba7e.png
[SouthEast 3]: /images/20220713/0d6c24b000dd44808d14fb41d53126ca.png
[SouthEast 4]: /images/20220713/4ccbd49a84864fd4a4de5263c54e7924.png
[SouthEast 5]: /images/20220713/85e3f47c9a2a4700a8e94ec4e0b01341.png