第 3 章 栈和队列

本章重点复习栈和队列这两种特殊的受限线性表栈的核心是“后进先出（LIFO）”，队列的核心是“先进先出（FIFO）”掌握它们在不同存储结构（顺序与链式）下的操作特性，以及括号匹配、表达式求值、卡特兰数等典型应用是本章复习的关键

栈

顺序栈（顺序存储结构）

• 存储结构：用一段连续存储单元（数组）存放栈元素
• 关键指针：常见做法 top 指向当前栈顶元素位置，或指向栈顶元素的下一位置（两种约定均可，需配套一致）
• 时间复杂度：入栈、出栈、取栈顶均为 $O(1)$
• 空间特性：需要预先分配容量 MaxSize，可能产生空间浪费或容量不足

易错点：溢出

• 上溢（overflow）：栈满仍入栈（越界）
• 下溢（underflow）：栈空仍出栈（非法）

共享栈

• 核心思想：两个栈共享同一数组空间，分别从两端向中间增长
• 优点：在总空间固定时，能更充分利用存储空间；当一个栈空而另一个栈满的情况减少
• 满栈判定：两栈顶指针相遇（或满足相邻条件，依约定而定）

链栈（链式存储结构）

• 存储结构：用单链表实现，通常把表头作为栈顶以便 Push/Pop 在表头进行
• 栈顶指针：指向栈顶结点
• 优点：
  • 不需要预先分配固定容量，理论上只受限于可用内存
  • 入栈/出栈无需移动大量元素
• 时间复杂度：入栈、出栈、取栈顶均为 $O(1)$；额外指针域带来一定存储开销

栈相关常见结论小结

核心特性：栈是受限线性表，核心特性：LIFO (Last In First Out) 顺序栈与链栈的基本操作复杂度均为 $O(1)$，差别主要在空间管理方式（固定容量 vs 动态分配）实现中需做边界检查与错误处理

栈的典型应用与要点

括号匹配

• 思想：扫描表达式，遇到左括号入栈，遇到右括号则与栈顶左括号进行匹配并出栈
• 关键结论：
  1. 扫描结束时栈必须为空才匹配成功
  2. 扫描中任何时刻出现“需要出栈但栈空”则匹配失败

表达式求值与表达式转换

三种常见表示

• 中缀：运算符在中间，日常书写
• 后缀/逆波兰式 (RPN)：运算符在后，便于用栈求值
• 前缀：运算符在前

中缀转后缀逻辑

• 约定：运算符有优先级（如 * / 高于 + -），多数二元运算符是左结合
• 准备：一个输出序列和一个运算符栈
• 从左到右扫描：
  • 遇到操作数：直接追加到输出序列
  • 遇到左括号 (：入运算符栈（隔断作用）
  • 遇到右括号 )：反复弹出栈顶运算符到输出序列，直到弹出左括号（左括号不输出）
  • 遇到运算符 op：
    • 当栈非空，且栈顶运算符 topOp 优先级高于 op，或优先级等于 op 且 op 是左结合，则将 topOp 出栈并追加；重复直到不满足条件或遇到左括号
    • 然后将 op 入栈
• 扫描结束：将运算符栈中剩余的运算符依次弹出追加

后缀表达式求值

• 扫描：操作数入栈；遇到运算符则弹出两个操作数计算后再入栈
• 结束：结束时栈顶即结果

出栈序列计数（卡特兰数）

• 问题表述：对 $n$ 个元素按固定顺序 $1,2,...,n$ 依次入栈，在允许任意时刻出栈的前提下，一共有多少种不同的出栈序列？
• 结论：合法出栈序列的种类数为第 $n$ 个卡特兰数 $C_n = \frac{1}{n+1} C_{2n}^{n}$
• 推理思路：
  • 入栈记为 $+1$，出栈记为 $-1$共 $2n$ 步，最终高度回 $0$
  • 合法性约束：从起点出发的过程中，高度不能降到 $0$ 以下
  • 非法路径：通过反射原理，可证明非法路径数为 $C_{2n}^{n+1}$
  • 合法路径：$C_{2n}^{n} - C_{2n}^{n+1} = \frac{1}{n+1} C_{2n}^{n}$
• 递推形式： $C_0 = 1$ $C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k} \quad (n \ge 1)$
  含义：按“最后一次出栈对应的元素”将整体拆成左右两个相互独立的合法子结构

递归与函数调用栈 / 深度优先搜索 (DFS)

• 递归与函数调用栈：
  • 递归本质：把大问题分解为规模更小的同类子问题，依靠系统调用栈保存返回点与局部状态
  • 必须有递归出口（终止条件），深度过大可能导致栈溢出
• 深度优先搜索 (DFS)：
  • DFS 的“先走到底再回退”天然符合栈的 LIFO 特性
  • 递归 DFS 使用系统栈；非递归 DFS 使用显式栈保存待访问结点/状态

队列

循环队列

• 核心思想：数组首尾相接，指针按模运算循环移动：
  • front = (front + 1) % MaxSize
  • rear = (rear + 1) % MaxSize

判空与判满的方法： 循环队列必须解决“front == rear 时到底是空还是满”的二义性，常见三种方法：

1. 牺牲一个存储单元（最常用）：
   • 判空：front == rear
   • 判满：(rear + 1) % MaxSize == front
   • 可用容量：MaxSize - 1
2. 增加计数器 size：
   • 判空：size == 0
   • 判满：size == MaxSize
3. 增加标志位 tag：区分最近一次操作是入队还是出队

链队列（链式存储结构）

• 存储结构：用链表实现队列，通常设置 front 指向队头结点，rear 指向队尾结点
• 带头结点的链队列：判空常为 front == rear（都指向头结点）
• 优点：
  • 不需要预设容量，适合元素个数变化较大场景
  • 入队在尾部插入、出队在头部删除，均为 $O(1)$

队列的变形与应用要点

• 双端队列 (Deque)：
  • 两端允许进入，一端允许退出
  • 两端允许退出，一端允许进入
• 队列的常见用途：
  • 层次遍历 (BFS)：按层推进天然符合 FIFO，典型实现用队列保存待访问结点
  • 缓冲与调度：如打印队列、消息队列、CPU 就绪队列等