数据结构第 3 章：栈与队列——受限的线性表反而更有用
栈和队列在逻辑上仍然是线性表，只是限制了插入删除的位置：栈只允许在一端进出，队列只允许一端进另一端出。这个限制看起来是"能力变弱"，实际上是"语义变强"——正因为限制了，才能精确表达"后进先出"和"先进先出"这两种最常见的现实需求，也才能让复杂度降下来。
一、栈：后进先出（LIFO）
只允许在栈顶插入（push）和删除（pop），栈底固定。n 个不同元素入栈，可能的出栈序列有 C(2n,n)/(n+1) 种（卡特兰数），这个结论在选择题里反复出现。
顺序栈：用数组加一个 top 指针。约定 top 指向栈顶元素时，初始 top = −1，判空 top == -1，判满 top == MaxSize-1；约定 top 指向栈顶的下一个空位时，初始 top = 0，判空 top == 0，判满 top == MaxSize。两种约定写法不同但都对，考试要看清题目用的是哪一种。
链栈：用单链表实现，插入删除都在表头做，所以不需要头结点，push 就是头插。链栈不存在栈满问题（除内存耗尽）。
共享栈：两个栈共用一个数组，分别从两端向中间长。栈满条件是 top1 + 1 == top2。这样能把空间利用率提高一倍，适合两个栈此消彼长的场景。
二、栈的应用：为什么每个程序员都要懂栈
- 括号匹配：遇左括号入栈，遇右括号出栈比对。结束时栈空才算匹配。O(n)。
- 表达式求值：先把中缀表达式转成后缀（逆波兰）表达式，再用栈求值。转后缀时用栈暂存运算符，按优先级出栈。这是编译原理里表达式分析的雏形。
- 递归：递归本质就是系统用函数调用栈保存现场。汉诺塔是最典型的例子——n 个盘子要移动 2ⁿ−1 次，递归式是 T(n) = 2T(n−1) + 1，解得 O(2ⁿ)。递归深度就是栈的深度，深度过大会栈溢出，这也是为什么递归要能改写成非递归（显式用栈）。
- 函数调用、撤销操作、浏览器后退：都是栈的语义。
三、队列：先进先出（FIFO）
只允许队尾入队、队头出队。
顺序队列的假溢出：用数组加 front/rear 指针时，随着出队 front 前移，前面空出来的位置无法再利用，rear 到数组末尾就"溢出"了——但数组其实没满。解决办法是把它变成循环队列。
循环队列的四个关键公式（用"牺牲一个单元"的经典约定，MaxSize = m）：
- 初始：
front = rear = 0 - 判空：
front == rear - 判满：
(rear + 1) % m == front - 元素个数：
(rear − front + m) % m
入队：rear = (rear+1) % m 后存值；出队：取值后 front = (front+1) % m。
如果不愿意牺牲那个单元，就要另外用一个计数器 count 或标志位 tag 来区分队空队满——"队空和队满时 front 都等于 rear"是这里唯一的歧义来源，所有方案都是为了消掉这个歧义。
链队列：需要队头指针和队尾指针，通常带一个头结点。出队是删头结点的后继，入队是尾插，都是 O(1)。链队列不会满（除内存耗尽）。
双端队列（deque）：两端都能进出，是很多算法（滑动窗口最值）的基础。
四、队列的经典应用
- 素数环：把 1~n 排成一个环使相邻两数之和为素数。用回溯 + 队列/递归枚举，是"搜索类问题"的入门例子。
- 停车场管理：车辆进场入队、离场时让出通道上的车进临时栈再复原，是"栈 + 队列配合"的经典建模题。
- BFS、任务调度、缓冲区：后面第 6 章图的广度优先遍历就是队列驱动的。
易错点与选择题高频点
- 判断"某个出栈序列是否合法"：用模拟法，按入栈顺序压入，随时比对出栈序列。
- 循环队列元素个数公式
(rear − front + m) % m，别写成rear − front。 - 共享栈判满
top1 + 1 == top2。 - 递归与栈的关系：递归一定可以用栈改写为非递归，但改写后代码可读性通常下降。
- 队列判空判满在循环队列和链队列里完全不同，链队列判空是
front == rear，且没有判满。
这一章在整门课里的位置
第 2 章的链表是本章的实现基础（链栈、链队列都是单链表）。本章的栈和队列又是第 5 章树遍历（递归/栈）、第 6 章图遍历（DFS 用栈、BFS 用队列）的工具。遍历算法的差异，本质就是"用栈还是用队列"的差异——这句话在第 6 章会变得非常具体。
补充：四种实现的复杂度与选型对照
栈和队列都是"操作受限的线性表"，所以实现方式就是第 2 章的两种存储方式各来一遍。选型的判断标准只有一条：长度是否可预知、是否要求严格 O(1) 且无额外指针开销。
| 实现 | 入/出复杂度 | 空间 | 判满条件 | 适用 |
|---|---|---|---|---|
| 顺序栈 | O(1) | 预分配，可能溢出 | top == MaxSize-1 | 深度可预估（如表达式求值） |
| 链栈 | O(1) | 每结点一个指针开销 | 无（除内存耗尽） | 深度不可预估、频繁进出 |
| 循环队列 | O(1) | 预分配 | (rear+1)%m == front | 固定缓冲、生产者消费者 |
| 链队列 | O(1) | 每结点一个指针开销 | 无 | 长度变化大、任务调度 |
一个容易被忽略的区别：顺序栈和循环队列的"满"是必须处理的边界，而链式实现永远没有满的问题——这也是为什么嵌入式与高并发场景更倾向链式（不会因为缓冲区满而丢数据，只是内存吃紧）。
另外要记住：栈和队列的插入删除都只在端点进行，所以都没有"按位置插入"的开销，平均复杂度都是 O(1)。这一点和线性表完全不同，也是它们能被用作底层结构（递归、BFS）的原因。
本篇是《数据结构与算法（93 讲）》第 3 章的知识点摘要。完整板书与代码见 课程页；上一章 线性表，下一章 串与数组。
相关课程
这篇笔记涉及的主题，我录过对应的视频课程：
- 数据结构与算法（93讲） 93 讲