写在前面

栈和队列是两种首先的线性数据结构。前者只能从一段插入和弹出元素,后者只能从一端插入元素,另外一端弹出元素。它们底层都可以分别用数组和链表来实现,主要的操作有 push 和 pop 两个。尤其是对于队列来说,它在基础形式上有很多的变形,如循环队列,阻塞队列,优先级队列等。之所以在数组和链表上实现者这两种数据结构,是因为它们的操作都符合一些特定的场景,也符合人类思考事物的一些思维。当我们使用它来描述一些较为复杂问题的时候,有很大的帮助,如操作系统中的生产者和消费者模型,从计算机的角度看待如何求不定式的值以及如何判断括号是匹配的。

栈和「栈」

提起栈,我们想到的可能不光是一种数据结构。在操作系统的内存中也存在着「栈」,它是一段真实的物理存储区。主要用来存储函数调用时的一些局部变量。栈的内存地址是从高向低扩展的,原因就是它借助了数据结构中栈的思想:后进先出。与「栈」相对的另外两种类型的存储区是堆和静态存储区。前者可由用户通过一些库函数在堆内存中分配一定的空间来进行使用,典型的就是 malloc 和 new。后者则用来存储一些全局变量,静态变量,常量等。

之所以使用栈来存储函数调用的局部变量,是因为函数的调用存在着「递归」关系,这个递归的层数可大可小。多层嵌套且后面的层先计算出结果的特点是非常符合栈这种数据结构的特点的:后进先出。而且,栈的操作:入栈,出栈也非常的方便。即使是想清空栈,也直接调整一下栈顶指针即可。

扩容栈

我们无法在使用一个数据结构之前就能够预判它之后所需要的空间。所以说,我们需要实现一定的扩容机制。对于链表的实现来说,直接在队尾插入新节点即可。 但是对于数组来说,可能涉及到要移动元素。因为数组的内存空间在定义时就已经确定了。不过由于移动元素的操作并不是每一次入栈和出栈都会发生,所以通过「摊还时间分析法」可以简单的分析出,即使是有扩容操作,入栈和出栈的时间复杂度仍然为 O(1)。

无论使用链表实现栈还是数组,都需要考虑以下几个问题:

  1. 空间复杂度:主要是针对链表而言,因为它需要额外存一个指针
  2. 内存溢出:无限制的扩张,最终可能导致存储空间被占用光
  3. 内存泄漏:不适用的空间没有及时回收,导致内存泄漏

其中对第一点来说,如果我们对空间复杂度要求比较高,那么我们应该选择数组来实现。而对 2,3点来说,就得在实现中具体做一些限制,防止这种情况的发生。

栈的应用方式

对于栈的应用来说,一般是通过两种形式:

  1. 两个栈配合:实现队列,浏览器页面的回退功能,表达式求值,括号匹配
  2. 单个栈:逆序输出一个单项序列

队列

对于队列来说,唯一比栈复杂的地方就是它需要维护两个游标:一个指向队列头部,一个指向队列尾部。随着出队和入队操作的执行,这两个游标的位置要随之改变。更为复杂的是如何判断两个临界的条件:

  1. 队列满
    1. 真满
    2. 假满
  2. 队列空

我们将指向队列头部的游标命名为 head, 指向队列尾部待插入元素位置的游标为 tail。

队列满

真满

一个真正将申请的空间全都填满的队列有如下特点:

  1. tail 已经到了之前申请空间的尾部了,无法再继续向后移动
  2. head 仍然指向整个数据结构中的首地址的位置

之所以这么判断,是和 tail,head 的操作有关的。入队操作会引起 tail 向后移动,出队操作会引起 head 向后移动。转换到代码层面上,可以如下表示:

1
head == 0 && tail == n // 队列满

假满

一个假满的队列,是在有限的内存空间中,tail 已经移动到尾部了,但是 head 没有在首地址的位置。因为入队操作一直以来操作的都是 tail,当发现 tail == n 的时候,就认为队列满了,但是其实由于有出队操作的执行,还是有空余空间的。所以,这种就是假满的情况。

1
head != 0 && tail == n // 队列假满

假满的状态一般都要伴随着「数据迁移」。就如同之前我们聊数据这种数据结构的时候,为了保证它的顺序存储和连续存储的特性,我们时不时的要「整理碎片」。

队列空

在创建队列且未被使用的初始状态,head 和 tail 通常都赋值为数据结构的首地址。这证明在首尾指针之间没有任何的元素。所以,这也是判定队列为空的条件。

1
head == tail // 队列空

循环队列

循环队列的出现,解决了一个很重要的问题:如何在不进行「数据移动」操作的前提下最大限度的利用队列的内存空间。下面我们通过数组实现循环队列的例子来举例。

通过上面对普通队列的描述,我们可以知道,实现队列最关键也是最容易出错的地方就是两个临界条件:队满和队空。其中对空这个临界条件在循环队列中仍然可以按照之前的标准进行判断。但是队满就不一样了。

上述图片是一个循环队列队满的状态。细心的你一定会发现,这命名还有一个空余空间没有用,为什么说他已经满了?此时,你可以结合对空的临界条件,就可以知道,如果我们不预留这个一个元素空间的话,有一个地方是矛盾的:判断队满和对空的条件重合了: head == tail。而且,由于在这种环形的数据结构中,tail 可以无限制的移动,所以之前的队满临界条件就不生效了。

既然上面的图描述的就是队满的情况,那么如何将它固化成一个临界条件呢:

1
tail + 1 == head

看起来这样的就大功告成了。但是我们还漏掉了一点,就是 tail 如果一直+1的移动,可能会超出数组的边界。那么如何让他在到达边界的地方回到首部位置呢?答案是取余数。

1
(tail + 1) % n == head