03 栈与队列
栈和队列都是操作受限的线性表：栈只准从一头进出（后进先出 LIFO），队列一进一出（先进先出 FIFO）。限制越强，用途越专——本章一半在讲"它们能干什么"，一半在讲 408 的经典算术题（出栈序列数、循环队列判满）。
一、栈：后进先出
栈的基本盘
- 只在栈顶操作：push/pop/peek
- 顺序栈：
data[] + top；top 指向栈顶元素时初始 top=-1，push 先++top再放（若 top 指向栈顶下一格则初始 0，顺序反过来）——两派约定，读题先看约定 - 共享栈：两个栈共用一个数组，一个从底下往上长、一个从顶上往下长，栈顶相遇（top1+1==top2）才满——空间利用率翻倍的巧思
- 链栈：单链表 + 头插法（头即栈顶），无栈满问题
卡特兰数：n 个元素的出栈序列数
n 个元素依次进栈，任意时刻可出栈——合法的出栈序列总数：
| n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 合法出栈序列数 | 1 | 2 | 5 | 14 | 42 |
💡 n=3 时 5 种：abc、acb、bac、bca、cab 不行（a、b、c 依次进，c 先出后不可能 a 在 b 前？验证：c 先出 → 栈里 b、a，只能 b 后 a → cba✅）。经典陷阱题："n 元素进栈，出栈序列中不可能出现…"——用"在栈里，先入者后出"这条规则手推即可。
⚠️ 括号匹配的有效组合数、二叉树形态数（05-树与二叉树）都是同一个卡特兰数——408 喜欢跨界考。
栈的三大应用
- 括号/符号匹配：左括号进栈，右括号弹栈配对——编译器词法分析的日常
- 表达式求值：见下文中缀转后缀
- 函数调用栈：每次调用压一个栈帧（参数、局部变量、返回地址）——递归深度就是栈深，"栈溢出 StackOverflow"的字面来源；OS 的用户栈就是它
⚠️ 中断现场保护（计组 IO）也用系统栈——压栈/弹栈是硬件级操作。
中缀转后缀（手算例题）
后缀（逆波兰）：运算符写在操作数后——无括号、无优先级歧义，一遍扫描就能算。
例：A + B * C - (D / E + F) 转后缀
口诀：操作数直接输出；运算符看栈顶——栈顶优先级 ≥ 当前，就先弹；左括号只被右括号弹。
A→ 输出 A+→ 栈空，进栈[+]B→ 输出 A B*→ 栈顶+优先级低，*进栈[+ *]C→ 输出 A B C-→ 栈顶*≥-，弹*；栈顶+≥-，弹+；-进栈[-]→ 输出 A B C * +(→ 进栈[- (]D / E→ 输出 A B C * + D E，/进栈[- ( /]+→/弹出，+进栈[- ( +]→ 输出 … D E /F→ 输出 … F)→ 弹到左括号为止：弹+，丢(→ 输出 … F +- 结束，弹光：弹
-→ 输出 … −
结果：A B C * + D E / F + - ✅
求值：后缀式用栈扫一遍，遇数进栈、遇符弹两个数算完再进——[(A+ (B*C)) − ((D/E)+F)] 结构自明。
二、队列：先进先出
顺序队列的死缺陷 → 循环队列
顺序队列出队后** front 指针前进、前面空间报废**（假溢出）→ 把数组首尾接成环：
// 牺牲一个单元的约定（最常用）
front 指队首元素；rear 指队尾后一格
入队: rear = (rear + 1) % MAXSIZE
出队: front = (front + 1) % MAXSIZE
循环队列判满三法（408 必考）
| 方法 | 队满条件 | 队空条件 | 代价 |
|---|---|---|---|
| ① 牺牲一个单元 | (rear+1) % MAX <mark> front |
rear </mark> front |
最常用；少存 1 个元素 |
| ② 增设 size 变量 | size <mark> MAX |
size </mark> 0 |
多维护一个计数器 |
| ③ 增设 tag 标志 | 入队后 tag=1 且 rear==front |
出队后 tag=0 且 rear==front |
tag 记录"最后一次是入还是出" |
元素个数公式（无论哪种约定，背）：
💡 例题：MAX=10，front=3、rear=1 → 个数 = (1−3+10)%10 = 8。
⚠️ top/rear 指向的约定不同，判空判满就不同——读题先抠"rear 指哪"，这是 408 最阴的坑。
双端队列与衍生（了解）
- 双端队列 deque：两头都能进出；两端限制一个方向就是"输出受限/输入受限队列"
- 考题：给一串输入输出序列，判断"能否由该受限队列产生"——手动模拟进出即可
三、队列的三大应用
- 缓冲区/任务排队：打印队列、消息队列（Kafka/RabbitMQ 的思想原型）——削峰填谷
- BFS 广度优先搜索（图）：层序遍历的骨架
- 页面置换 FIFO 算法（OS 内存管理）、CPU 就绪队列（CPU 调度：FCFS 就是队列，时间片轮转也是队列）
💡 栈和队列的哲学：栈是"最近的优先"（时间逆序），队列是"先来的优先"（公平）——CPU 调度策略之争（优先级 vs 公平）在数据结构层面就是这两兄弟。
四、特殊矩阵的压缩存储（顺手收拾）
对称矩阵只存下三角：n(n+1)/2 个元素；下标 i,j（1-based，i ≥ j）→ 一维下标
- 三对角矩阵存 3n−2 个
- 稀疏矩阵：三元组表 (行, 列, 值) 或十字链表
- ⚠️ 408 常考"给 i,j 求一维下标"——记公式 + 用 i=2,j=1 代入验证（k=1），比背推导快
五、盲点自测
- 共享栈什么时候满？（top1+1 == top2，两栈顶相遇）
- 4 个元素入栈，合法出栈序列共几种？（卡特兰 C₄=14）
- 后缀式求值用栈：遇运算符弹几个数？先弹的是左操作数还是右？（2 个；先弹的算右操作数）
- 循环队列 MAX=8，front=5、rear=2，元素几个？((2−5+8)%8=5)
- 判满三法各自的代价？（牺牲空间 / size 维护 / tag 维护）
- 中断现场压栈用的是哪种结构？（系统栈——LIFO）
- BFS 和 CPU 调度 FCFS 的共同骨架？（队列 FIFO）
六、动手玩
# 用栈把后缀式求值一遍（对照本文例题）
def eval_postfix(tokens):
st = []
for t in tokens:
if t in '+-*/':
b, a = st.pop(), st.pop() # 先弹的是右操作数！
st.append({'+': a+b, '-': a-b, '*': a*b, '/': a/b}[t])
else:
st.append(t if not t.isdigit() else int(t))
return st[0]
# A=2, B=3, C=4, D=8, E=2, F=5 → 2+12-(4+5) = 5
print(eval_postfix([2,3,4,'*','+',8,2,'/',5,'+','-'])) # 5
# 循环队列：验证个数公式
MAX = 10
front, rear = 3, 1
print((rear - front + MAX) % MAX) # 8
💬 评论