跳至正文

栈与队列

栈与队列

核心定义

栈 只允许在 栈顶 进行插入和删除，遵循 后进先出（LIFO）；队列 只允许在 队尾入队、队头出队，遵循 先进先出（FIFO）。栈更像”回退栈”，队列更像”排队系统”。

栈和队列的本质都是 操作受限的线性表，只能在特定端操作。

顺序栈 用数组实现，栈顶指针 top 初始为 −1-1（或 00，取决于约定）。入栈时先 top++ 再赋值；出栈时先取值再 top—。

链栈 用链表实现，栈顶在 头结点位置，入栈出栈都在头部操作，时间 O(1)O(1)。

顺序队列 用数组实现，存在 假溢出 问题——前面有空位但 rear 到底了。

循环队列 用于解决假溢出，判空条件为 front==rear\text{front} == \text{rear}，判满条件为 (rear+1)%MaxSize==front(\text{rear} + 1) \% \text{MaxSize} == \text{front}（牺牲一个存储单元法）或使用 size 计数器 区分。

链队列 用链表实现，不存在假溢出，队头在 front 指针处，队尾在 rear 指针处。

共享栈 是两个栈共用一个数组，分别从 两端向中间增长，可以更充分利用空间。栈满条件为 top1+1==top2\text{top1} + 1 == \text{top2}。

双端队列 允许在 两端都可以进出，是栈和队列的推广。若只允许一端进出则退化为 栈，若只允许一端进另一端出则退化为 队列。

函数调用会使用栈保存 返回地址和局部变量，广度优先搜索会使用队列 逐层推进。

关键细节 / 操作步骤

基本操作与复杂度

  1. 栈操作关注 栈顶，进出同端，入栈出栈均 O(1)O(1)。
  2. 队列操作关注 队头 与 队尾，入队 rear 后移，出队 front 后移。
  3. 循环队列判空满要结合 front、rear 和容量约束，先固定一个判空判满规则再计算。
  4. 若题目问时间复杂度，栈和队列的基本操作通常是 O(1)O(1)。

存储实现与边界

  1. 若题目问顺序存储的溢出判断，先确认是否为 假溢出（有空间但无法使用）。
  2. 若题目问链式实现，关注 指针操作 和边界情况（空队列时 front 和 rear 都指向 头结点）。

应用场景选型

  1. 若题目问 表达式求值 或 括号匹配，先想到栈——右括号必须与栈顶左括号匹配，不匹配则 语法错误。
  2. 若题目问 中缀表达式 转 后缀表达式，使用栈的规则是 运算符按优先级入栈出栈，操作数直接输出。
  3. 若题目问 递归模拟，先想到栈——递归是 控制流，栈是 实现支撑，递归深度对应栈的最大深度。
  4. 若题目问广搜（BFS）或缓冲排队，先想到队列。
  5. 若题目问深度优先搜索（DFS），常配 栈（或递归）。
  6. 若题目问共享资源调度，队列常用于 等待顺序管理。

计数与公式

  1. 若题目问双端队列的应用，注意 输入受限 和 输出受限 两种变形。
  2. 若题目问栈的最大深度，等于 同时存在的未完成调用数。
  3. 若题目问循环队列当前元素个数，公式为 (rear−front+MaxSize)%MaxSize(\text{rear} - \text{front} + \text{MaxSize}) \% \text{MaxSize}。
  4. 若题目问栈的合法出栈序列，核心是 后进先出——先入栈的元素不可能先于后入栈的同栈元素出栈。对于 nn 个不同元素入栈，合法出栈序列数为 1n+1(2nn)\frac{1}{n+1}\binom{2n}{n}（Catalan 数）。

⚠️ 易错辨析 循环队列不是简单把数组首尾接起来就完事，空和满的判定必须统一规则，否则会把”满”误判成”空”。队头指针 front 指向 队头元素，队尾指针 rear 指向 队尾元素的下一位置（牺牲单元法）。递归和栈密切相关，但递归不等于栈本身——递归是控制流，栈是实现支撑。队列中的”假溢出”说明前面有空位但 rear 到底了，循环队列就是为解决这个问题而生。共享栈的两个栈从两端向中间增长，当 top1+1==top2\text{top1} + 1 == \text{top2} 时栈满。反例：若循环队列不牺牲一个空位也不用计数器，则 front == rear 时无法区分空还是满。

💡 技巧与口诀 口诀：栈看”回退”，队看”排队”；递归常配栈，广搜常配队。适用场景：题目只要出现”撤销、括号匹配、递归、表达式”就优先想栈；出现”层次遍历、缓冲、等待”就优先想队列。中缀转后缀的核心是 遇到更高优先级运算符先弹出栈中运算符。若题目问循环队列容量计算，要先确认是否 保留一个空位——可用容量为 MaxSize−1\text{MaxSize} - 1。

📝 真题闭环 题目：循环队列为什么要引入判空判满规则？若队列容量为 MaxSize，牺牲一个存储单元时判空和判满条件分别是什么？该队列最多能存储多少个元素？

解题思路：审题抓”为什么要引入”，切入点是 避免假溢出和歧义；方法选择为数组边界分析；计算关键点是首尾指针回绕后需要统一规则判断状态；易错防范是把满和空状态写反。

答案：判空条件为 front==rear\text{front} == \text{rear}，判满条件为 (rear+1)%MaxSize==front(\text{rear} + 1) \% \text{MaxSize} == \text{front}，最多存储 MaxSize−1\text{MaxSize} - 1 个元素。

// T=O(1) S=O(1)
int is_empty(int front, int rear) {
    return front == rear;
}
cd ..