面试指北：算法与数据结构（四）栈与队列

上次聊到数组与链表，它们都是线性表，数组与链表的本质区别是内存是否连续，进而得出结论：数组可以在 O(1) 时间复杂度进行随机访问，但是对内存要求严苛；链表访问元素时间复杂度为 O(n)，但是对内存要求低。

今天来介绍另外两个线性表中的数据结构：栈和队列。

栈 Stack

栈是一种线性表，只有前后关系，但是相对于数组和链表来说，其元素的操作是受限的。栈只允许在一端进行元素的插入、删除操作，往栈中放入元素我们称之为压栈操作，从栈中取出元素我们称之为出栈。我们可以把栈看作是一个一端开口的羽毛球筒，我们压栈、出栈操作数据的过程，就是我们从筒中放入、取出羽毛球的过程。当然，栈是一种抽象的数据结构，我们在实现它时，既可以使用数组，也可以使用链表。

接下来我们看一下栈的使用情景。

浏览器网页前进后退

我们经常会使用浏览器浏览网页，网页中有很多超链接可以跳转到下一个页面。而有时我们希望能够返回上一个页面继续浏览，再返回上一个页面之后，我们还可能再回到刚才的子页面。

使用两个栈就可以实现这种能够随意前进后退的网页浏览了。

我们把一开始打开的网页压栈放入栈 a，如果此时点击网页中的链接查看下一个页面，那我们把子页面继续放入栈 a。当我们返回时，把子页面从 a 中出栈，放入栈 b。这个时候我们关闭页面，继续从 a 中出栈放入栈 b 即可。如果我们点击前进按钮，则去栈 b 中出栈即可。也就是说，如果我们把依次打开过的网页放入栈 a 维护，回退的界面放入栈 b 维护。点击后退按钮时，查询栈 a，有页面则出栈，放入栈 b，没有则无法后退；点击前进按钮时，查询栈 b，有页面则出栈，没有则无法前进。

函数调用栈

基本每一个编程语言中，都存在函数的概念。一个函数可以调用另外一个函数，那么函数之间的调用是如何实现的呢？也是用栈。

以 Java 为例，我们编写 Java 代码之后，是编译为 class 字节码，然后交给 Java 虚拟机执行。在 Java 虚拟机中，是使用一个栈来完成函数调用的，每一个函数在栈中所占有的空间称为栈帧。Java 入口函数为 main 函数，执行时先将 main 函数入栈，此时栈帧中会保存该函数的局部变量、操作数栈、动态连接、方法返回地址等内容。当 main 函数调用一个子函数 add 时，虚拟机会继续将 add 函数相关内容压入栈顶，add 函数执行完毕后会出栈，此时 main 函数处于栈顶，会继续执行 main 函数。

这个例子我们可以看到，对于基础数据结构的理解，可以帮助我们了解平时常用语言、框架的实现细节，对于我们深入学习计算机知识很有帮助。除了以上两个例子之外，栈还可以用来做表达式求值、括号匹配等，感兴趣的话可以自行了解。

队列 Queue

队列和栈一样，也是一种操作受限的线性表数据结构。栈只能在一端进行插入和删除操作，队列则是在一端进行删除操作，称为出队，在另一端进行插入操作，称为入队。

和栈一样，队列也可以使用数组或者链表来实现。当我们使用数组来实现时，需要维护两个变量 head、tail 标识队列的头部和尾部。入队时，元素放入数组现有元素的末尾，tail 往后移动一位。出队时，首个元素删除，head 往后移动一位。此时会出现这样一种情形：当我们经过不断的入队和出队之后，head、tail 会不断的往后漂移，当 tail 到达数组尾部时，没办法再进行入队操作，但是很可能 head 之前还有空间。这就导致空间浪费。此时我们可以通过每次出队都把所有数据往前搬移一位，也可以通过 tail 到达数组末尾时，搬移所有数据到数组头部解决问题，但是频繁的搬移操作会浪费性能。

由此导致了循环队列的产生。循环队列的关键是，把数组看成一个环状结构。head、tail 到达数组末尾时，仍可以回到头部的位置。此时使用 tail 尾部这个词就不太合适，改用 rear 后部更好。如下图，入队出队的过程，就是操作 head、rear 位置的过程。在这个环中，我们可以不断的转圈修改其位置，而不会出现上述局面，也就把我们从频繁搬移数据中解绑，减少性能消耗。

但是我们的底层实现还是数组，这里的关键问题有两个：

1.如何在 rear 到达数组尾部时，处理 rear 的位置？2.如何判断队空和队满？

对于第一个问题我们可以使用求余操作来解决问题。普通队列我们是直接 rear++ 操作位置，现在我们改成 rear = (rear + 1) % array.length - 1 来操作即可。当然 head 也是如此。

对于第二个问题，普通队列我们通过 head == 0 && tail == array.length 来判断队满，head == tail 来判断队空。循环队列还是使用 head == tail 判断队空，队满的条件就要改成 (tail + 1) % array.length == head。

另外一种队列是阻塞队列。阻塞队列就是在队列基础上增加了阻塞操作。当队空的时候，从队列取出数据时会阻塞；当队满时，在队列中插入数据会阻塞。可以发现，阻塞队列跟我们常说的 生产者-消费者模型 逻辑基本一致。

还有一种比较常用的队列是优先队列，即优先级更高的元素优先出队，该队列的实现涉及到完全二叉树、大顶堆、小顶堆相关知识，我们后续会涉及到。

总结

我们可以看到栈和队列是一种抽象的数据结构，定义一种操作规则，然后应用到对应的场景之中。这两种数据结构的操作规则和其应用场景是契合的。我们在学习算法和数据结构时，了解其优点和缺点，进而了解其应用场景是十分重要的。没有最好的数据结构和算法，只有在某种场景下更加适合的数据结构与算法。