栈和队列

# 栈和队列

队列和栈都是操作受限的线性表：前者先进先出，后者先进后出。

# 栈

# 栈是什么

在 LIFO (后进先出) 数据结构中，将首先处理添加到队列中的最新元素。

栈是一个 LIFO (后进先出) 数据结构。栈是一种 “操作受限” 的线性表，只允许在一端插入和删除数据。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

img

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选 “栈” 这种数据结构。

从栈的定义可以看出，栈只支持两个基本操作：入栈 push() 和 出栈 pop() ，也就是在栈顶插入一个数据和从栈顶删除一个数据。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是 O(1) 。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

# 为什么需要栈

相比数组和链表，栈只是对操作进行了限制，似乎并没有任何优势。为什么不直接使用数组或者链表？为什么还要用这个 “操作受限” 的 “栈” 呢？

特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。

# 栈的应用场景

（1）函数调用栈

img

（2）表达式求值

img

（3）表达式匹配

可以借助栈来检查表达式中的括号是否匹配

# 队列

在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。

队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。

# 什么是队列

队列：先进先出的线性表。

队列是一种 “操作受限” 的线性表，只允许在一端插入数据，在另一端删除数据。

队列的最基本操作：入队 enqueue() ，放一个数据到队列尾部；出队 dequeue() ，从队列头部取一个元素。

img

队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

队满的判断条件是 tail == n ，队空的判断条件是 head == tail 。

# 循环队列

循环队列是一种较为特殊的队列。

循环队列的要点是确定好 队空和队满的判定条件。

在用数组实现的非循环队列中，队满的判断条件是 (tail+1) % n == head ，队空的判断条件是 head == tail 。

img

# 为什么需要队列

为什么需要队列和为什么需要栈，是同样的道理，参考 为什么需要栈

# 队列的应用场景

（1）阻塞队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是：

• 在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；
• 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

img

img

（2）并发队列

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue ()、dequeue () 方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或者取操作。实际上，基于数组的循环队列，利用 CAS 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

# 参考资料

• 数据结构与算法之美
• Leetcode：栈和队列

数据结构 线性表 栈 队列