栈1 物理结构和逻辑结构

什么是数据存储的物理结构呢？

如果把数据结构比作活生生的人，那么物理结构就是人的血肉和骨骼， 看得见，摸得着，实实在在。例如我们刚刚学过的数组和链表，都是内 存中实实在在的存储结构。

而在物质的人体之上，还存在着人的思想和精神，它们看不见、摸不 着。看过电影《阿凡达》 吗？男主角的思想意识从一个瘦弱残疾的人 类身上被移植到一个高大威猛的蓝皮肤外星人身上，虽然承载思想意识 的肉身改变了，但是人格却是唯一的。

如果把物质层面的人体比作数据存储的物理结构，那么精神层面的人格则是数据存储的逻辑结构 。逻辑结构是抽象的概念，它依赖于物理结构而存在。

下面我们来讲解两个常用数据结构：栈和队列。这两者都属于逻辑结 构，它们的物理实现既可以利用数组，也可以利用链表来完成。

后面还会学习到二叉树，这也是一种逻辑结构。同样地，二叉树也可以依托于物理上的数组或链表来实现。

2 什么是栈

要弄明白什么是栈，我们需要先举一个生活中的例子。

假如有一个又细又长的圆筒，圆筒一端封闭，另一端开口。往圆筒里放 入乒乓球，先放入的靠近圆筒底部，后放入的靠近圆筒入口。

那么，要想取出这些乒乓球，则只能按照和放入顺序相反的顺序来取，先取出后放入的，再取出先放入的，而不可能把最里面最先放入的乒乓球优先取出。

栈（stack）是一种线性数据结构，它就像一个上图所示的放入乒乓球的 圆筒容器，栈中的元素只能先入后出 （First In Last Out，简称FILO ）。最早进入的元素存放的位置叫作栈底 （bottom），最后进入的元素 存放的位置叫作栈顶 （top）。

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

栈的数组实现如下。

栈的链表实现如下。

那么，栈可以进行哪些操作呢？栈的最基本操作是入栈和出栈，下面让我们来看一看。

3 栈的基本操作1. 入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。

这里我们以数组实现为例。

2. 出栈

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

这里我们以数组实现为例。

入栈和出栈操作，时间复杂度分别是多少？

入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动，所以无论是以数组还是以链表实

现，入栈、出栈的时间复杂度都是O(1) 。

队列什么是队列

要弄明白什么是队列，我们同样可以用一个生活中的例子来说明。

假如公路上有一条单行隧道，所有通过隧道的车辆只允许从隧道入口驶入，从隧道出口驶出，不允许逆行。

因此，要想让车辆驶出隧道，只能按照它们驶入隧道的顺序，先驶入的 车辆先驶出，后驶入的车辆后驶出，任何车辆都无法跳过它前面的车辆提前驶出。

队列（queue）是一种线性数据结构，它的特征和行驶车辆的单行隧道 很相似。不同于栈的先入后出，队列中的元素只能先入先出 （First In First Out，简称FIFO ）。队列的出口端叫作队头 （front），队列的入口端叫作队尾 （rear）。

与栈类似，队列这种数据结构既可以用数组来实现，也可以用链表来实现。

用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素 的下一个位置 。

队列的数组实现如下

队列的链表实现如下

那么，队列可以进行哪些操作呢？

和栈操作相对应，队列的最基本操作是入队和出队。

队列的基本操作

对于链表实现方式，队列的入队、出队操作和栈是大同小异的。但对于数组实现方式来说，队列的入队和出队操作有了一些有趣的变化。

1. 入队

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

2. 出队

出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

如果像这样不断出队，队头左边的空间失去作用，那队列的容量岂不是越来越小了？例如像下面这样。

问得很好，这正是我后面要讲的。用数组实现的队列可以采用循环队列 的方式来维持队列容量的恒定。

循环队列是什么意思呢？让我们看看下面的例子。

假设一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组的末尾位置。这时又有一个新元素将要入队。

在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。

这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，将其放入数组的首位，队尾指针继续后移即可。

一直到（队尾下标+1）%数组长度 = 队头下标 时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。

这就是所谓的循环队列，循环队列不但充分利用了数组的空间，还避免了数组元素整体移动的麻烦，所以入队和出队的时间复杂度，也同样是O(1) 。

栈和队列的应用1. 栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。

例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。

栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻 松地回溯到上一级或更上一级页面。

2. 队列的应用

队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。

例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中次序的。

再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中， 再按照存入队列的顺序来依次抓取和解析的。

3. 双端队列

那么，有没有办法把栈和队列的特点结合起来，既可以先入先出，也可以先入后出呢？还真有，这种数据结构叫作双端队列 （deque）。

双端队列这种数据结构，可以说综合了栈和队列的优点，对双端队列来说，从队头一端可以入队或出队，从队尾一端也可以入队或出队。

4. 优先队列

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。这种队列叫作优先队列 。

优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。关于优先队列的原理和使用情况，我们会在后面进行详细介绍。