Theory · Data Structure · Stack & Queue
受限的线性表：LIFO 与 FIFO 两条纪律 · 环形队列 · 单调栈与单调队列 —— 从括号匹配到滑动窗口最大值
后进先出：函数调用、括号匹配、DFS、撤销——"最近的先处理"
先进先出：BFS、任务调度、消息队列——"先来的先处理"
栈/队列装上"单调性"约束，从 O(n²) 暴力降到 O(n)——面试中级题钥匙
Why It Matters
你期待撤销的是刚才那一次。如果把编辑记录存进一个"先来先取"的清单，撤销键会去撤第 1 次编辑——功能直接是错的。撤销必须后进先出。
如果打印机也"后进先出"，最先提交的人会一直被后来者插队、永远打不出来。打印必须先进先出。
两件事用的都是"一个待处理清单"，差别只在从哪一端取。取错端不是慢一点，而是功能错——把 BFS 的队列换成栈，最短路的答案就不对了。所以这两条纪律要单独命名、单独学：栈（LIFO）和队列（FIFO）。
① 它们是出现频率最高的两个结构：函数调用、递归、DFS、括号匹配全是栈；BFS、线程池、消息队列全是队列；② 它们还能被改造成算法武器——加一条"内部保持单调"的规矩就能把暴力降一个数量级，见右侧。
Prerequisites & Glossary
| 术语 | 一句话理解（细节后面展开） |
|---|---|
| LIFO 后进先出 | Last In First Out：最后放进去的最先拿出来——一叠盘子 |
| FIFO 先进先出 | First In First Out：最先放进去的最先拿出来——排队买饭 |
| 栈顶 top | 栈唯一的出入口；push 压入、pop 弹出、peek 只看不取 |
| 队头 / 队尾 | 队列的出口 head / 入口 tail；enqueue 从队尾进、dequeue 从队头出 |
| 取模 % | 除法取余数；(i+1)%n 让下标走到末尾自动回到 0，是"成环"的全部魔法 |
| 假溢出 | 数组队列出队只挪头指针，前面空着却报"满了"——环形队列就是来治它的 |
| 背压 backpressure | 队列满了以后怎么办：阻塞生产者 / 丢弃 / 拒绝，属于业务决定的语义 |
| 均摊 amortized | 把偶发的大开销摊到多次操作上算平均值，得到"每次成本" |
| 单调 | 一列数只增不减（或只减不增）；本 deck 指"容器内部始终保持有序" |
| 双端队列 deque | 两端都能进出的容器；只用一端即栈，两端分工即队列 |
数组与链表 → 栈和队列都要"住"在其中之一里，本 deck 默认你知道两者代价
复杂度分析 → O(1)/O(n) 怎么读，"均摊"到底摊的是什么
栈和队列都是受限的线性表——限制只落在一处：允许从哪一端进、从哪一端出。
· 同一端进出 = 栈（"最近的先处理"）；
· 一端进、另一端出 = 队列（"先来的先服务"）；
· 两端都能进出 = 双端队列（前两者的超集）。
在上面的容器里额外要求"内部元素始终单调"，进出时顺手把"不可能再当答案的候选"清掉——这就是单调栈 / 单调队列。存储结构因此变成了筛选器，这是本 deck 后半场的全部内容。
Two Disciplines
把开场的撤销键和打印机画出来就是下面两张图：左边同端进出（栈），右边两端分工（队列）。
Stack · Implementation
| 操作 | 复杂度 | 说明 |
|---|---|---|
| push / pop / peek | O(1) | 全部在栈顶一端进行 |
| 搜索（任意元素） | O(n) | 栈不提供遍历语义 |
| 空间 | O(n) | 数组版有扩容预留 |
s = append(s, v) 入栈，v, s = s[len(s)-1], s[:len(s)-1] 出栈。扩容是均摊 O(1)（复杂度 deck），缓存又友好，链栈只在没有容量预期且频繁头插时才用。
缓存局部性好、内存紧凑；代价是偶尔扩容搬迁、预留空间浪费。现代工程默认选择。
天然无"满栈"、峰值内存按需；每节点 8B 指针开销 + 分配开销 + 缓存不友好。只在内存紧张或元素巨大时考虑。
Java Deque<Integer> s = new ArrayDeque<>()（官方已不建议用继承 Vector 的 Stack 类）；C++ std::stack（默认基于 deque）；Python 直接用 list。
栈操作全在一端，数组"尾部操作 O(1)"正好对上；队列两端操作，普通数组就不合适了——这正是下一页环形队列要解决的问题。
Circular Queue · Ring Buffer
Deque · Double-Ended Queue
两端都支持 O(1) 插入删除（pushFront/pushBack/popFront/popBack）。只在一端用就是栈，两端分工用就是队列。
① 双链表：实现最直接，指针开销大；② 块状数组：多个固定块（如每块 64 槽）用中间索引表串起来——Python collections.deque 就是它，兼顾两端 O(1) 与缓存局部性；Java ArrayDeque 用环形数组。
标准库没有 deque；container/list（双链表）或手写环形数组。GMP 调度器的本地运行队列是固定 256 的环形队列 + 偷一半语义（GMP deck）。
装上"值单调"约束的 deque 就是滑动窗口最大值的 O(n) 解法——第 10 页展开。
| 语言 | 实现 | 底层 |
|---|---|---|
| Python | collections.deque | 块状链表（64 槽/块） |
| Java | ArrayDeque / LinkedList | 环形数组 / 双链表 |
| C++ | std::deque | 块数组 + 中央映射表 |
| Go | container/list / 手写 | 双向循环链表 / 环形数组 |
Stack Applications
左括号入栈；右括号必须与栈顶的左括号配对——"最近的未匹配左括号"天然是 LIFO 语义。计数器数不出 [(]) 这种交错非法。
每层调用一个栈帧（参数、返回地址、局部变量）；递归就是隐式栈。爆栈（深递归）的标准出路：显式栈改迭代。
后缀（逆波兰）直接一个栈：操作数入栈，遇运算符弹两个算完压回。中缀转后缀：运算符栈按优先级进出，括号是优先级屏障。
后退栈 + 前进栈成对工作：跳转时把当前页压入"后退栈"并清空"前进栈"——两个栈就是完整的历史状态机。
递归DFS靠调用栈；显式栈版用 stack 存待访问节点。回溯的"撤销选择"正是出栈语义（回溯 deck）。
辅助栈与主栈同步：push 时若 ≤ 辅助栈顶则同步压入（或每步都压"当前最小"），pop 时同步弹——getMin 恒 O(1)。
debug.SetMaxStack）；但深递归的帧复制仍有成本，热路径上显式栈迭代化更稳。
Queue Applications
FIFO 保证"先入队的先扩展"——第 k 层全部处理完才轮到 k+1 层，层次性就是正确性。换成栈就退化成 DFS。
线程池的待办队列、日志异步落盘、削峰填谷。内存版最典型实现就是 Go channel：环形缓冲 + 两个等待队列 + 互斥锁（channel deck）。
Kafka/RocketMQ 把"队列"升级成分布式服务：持久化、分区并行、消费组、重试与回溯——解耦、削峰、异步三大价值（Kafka deck）。
网络收发包缓冲、令牌桶的令牌供给、打印队列；OS 的就绪队列/IO 队列同理——调度器的等待语义全是队列。
| 场景 | 为什么是队列 | 关键属性 |
|---|---|---|
| BFS | 保序 → 层次正确 | FIFO + visited 标记 |
| 线程池 | 任务公平排队 | 阻塞 + 唤醒 |
| channel | 协程间生产消费 | 环形缓冲 + 等待队列 |
| Kafka | 跨服务解耦削峰 | 持久化 + 分区 + 消费组 |
| 限流缓冲 | 瞬时洪峰排队 | 有界 + 满时拒绝/阻塞 |
Monotonic Stack
对每个元素问"下一个/前一个 更大/更小的元素是谁"。暴力是 O(n²) 双重扫描；单调栈一遍 O(n)。
栈里存还没找到答案的下标，其对应值自底向顶单调不增。新元素 x 到来：弹出所有严格小于 x 的栈顶——x 就是它们的"下一个更大元素"（相等的留下：x 并不比它们大）；然后 x 入栈等待自己的答案。
每个下标最多入栈一次、出栈一次，总操作 ≤ 2n——典型的摊还分析（复杂度 deck）。
下一个更大 → 递减栈（栈顶最小，比 x 小的才弹，相等别弹）；下一个更小 → 递增栈；前一个更小（84 题）→ 从左扫递增栈；循环数组（503）→ 遍历 2n 取模。
// 每日温度 (LC 739)：下一个更高温度隔几天 func dailyTemperatures(t []int) []int { ans := make([]int, len(t)) stack := []int{} // 存下标，温度递减 for i, v := range t { for len(stack) > 0 && t[stack[len(stack)-1]] < v { j := stack[len(stack)-1] stack = stack[:len(stack)-1] ans[j] = i - j // v 是 j 的答案 } stack = append(stack, i) } return ans // 栈里剩下的没有更大值，ans=0 }
Largest Rectangle · LC 84
Monotonic Deque · LC 239
deque 里存下标，对应值从头到尾单调递减——队头永远是当前窗口的最大值。
入（窗口右侧进 x）：从队尾把所有 ≤ x 的下标弹出——它们比 x 小又先过期，永远不可能再当最大；出（窗口左界滑过队头下标）：从队头弹出。
每个下标至多入队一次、出队一次 → 总操作 ≤ 2n。与单调栈同一套摊还论证。
堆（惰性删除过期下标）是 O(n log n)，好写但慢一档；单调队列 O(n) 且每步取最大 O(1)。面试先说堆再优化到队列，展示递进。
// 滑动窗口最大值 (LC 239) func maxSlidingWindow(a []int, k int) []int { dq := []int{} // 存下标，值递减 ans := []int{} for i, v := range a { // 1. 尾部：弹掉不可能是最大的 for len(dq) > 0 && a[dq[len(dq)-1]] <= v { dq = dq[:len(dq)-1] } dq = append(dq, i) // 2. 头部：弹出过期下标 if dq[0] <= i-k { dq = dq[1:] } // 3. 窗口成型后取队头 if i >= k-1 { ans = append(ans, a[dq[0]]) } } return ans }
From Ring Buffer To Channel
① 并发安全：多生产者/消费者时 head/tail 要互斥或原子操作；② 背压：满了是阻塞、丢弃还是拒绝——语义由业务定；③ 内存序：无锁实现要配 memory barrier。
hchan = 环形缓冲 buf + sendx/recvx 下标 + mutex + sendq/recvq 两个等待队列。有缓冲 channel 就是"阻塞版环形队列"：满则发送方挂进 sendq 睡眠，接收方唤醒它——背压语义内建。
手写环形队列：零依赖、自己管锁与背压；channel：拿到来锁、阻塞唤醒、select 多路复用，性能略低但安全得多。工程默认 channel，极致热路径才手写。
| 维度 | 环形队列（手写） | Go channel |
|---|---|---|
| 结构 | 数组 + head/tail 取模 | hchan：buf 环形 + 双等待队列 |
| 并发 | 自己加锁/原子 | mutex 内建 |
| 满时行为 | 自定义（阻塞/丢弃/拒绝） | 阻塞 → goroutine 挂 sendq |
| 多路复用 | 无 | select |
| 适用 | 热路径、固定拓扑 | 默认选择 |
LeetCode Shortlist
| 分组 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 基础栈 | 20 有效的括号 E · 150 逆波兰表达式 M · 155 最小栈 E | 20 是栈语义入门；155 用辅助栈 |
| 结构互转 | 232 用栈实现队列 E · 225 用队列实现栈 E | 232 要会均摊 O(1) 分析 |
| 单调栈 | 739 每日温度 M · 496 下一个更大元素 I E · 503 循环 M · 84 柱状图最大矩形 H | 739 是母题；84 加哨兵；503 遍历 2n |
| 单调队列 | 239 滑动窗口最大值 H | 尾弹头弹取头三步；对比堆解法 |
| 组合应用 | 42 接雨水 H · 224 基本计算器 H · 394 字符串解码 M | 42 三解法都值得写一遍 |
Cheat Sheet
| 需求里的信号词 | 结构 |
|---|---|
| 最近的 / 嵌套 / 成对 / 撤销 / 回溯 | 栈（括号、表达式、DFS、历史） |
| 先来先服务 / 逐层 / 缓冲 / 削峰 | 队列（BFS、线程池、channel、MQ） |
| 两端都要操作 / 窗口两侧 | 双端队列 |
| 下一个更大 / 更小、左右第一个更矮 | 单调栈 |
| 固定窗口内的最大 / 最小值 | 单调队列 |
| 要按权重 / 优先级取，不按到达序 | 堆（优先队列） |
| 环形队列 | 入 buf[tail]=v; tail=(tail+1)%n；空 head==tail；满 (tail+1)%n==head（牺牲一格）或另记 size |
| 两栈实现队列 | in 栈进、out 栈出，out 空才整体倒运；均摊 O(1)，单次最坏 O(n) |
| 最小栈 | 辅助栈同步压 min(v, 辅助栈顶)，getMin 恒 O(1)，空间换时间 |
| 找"下一个更大" | 递减栈（栈内自底向顶不增）：来了更大的就弹栈并给答案 |
| 找"下一个更小" | 递增栈；口诀：要找更大就先让小的等在栈里 |
| 栈的四步骨架 | 遍历 → while 弹栈 → 弹出时结算答案 → 当前入栈（末尾可加哨兵统一清栈） |
| 队列的三步骨架 | 尾弹（保单调）→ 头弹（去过期）→ 取头（拿答案） |
| 为什么 O(n) | 每个下标至多入一次、出一次，总操作 ≤ 2n（摊还） |
| 栈 push/pop/peek | O(1)（数组尾部或链表头部） |
| 队列 enqueue/dequeue | O(1)（环形取模，无搬移） |
| deque 两端操作 | O(1)（双链表 / 环形数组 / 块状数组） |
| 单调栈 / 单调队列全程 | O(n) 时间，O(n) 空间 |
Interview QA · Part 1
先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的翻回上一页速查表。
数组（动态）：缓存友好、内存紧凑、操作均摊 O(1)；链表：无满栈/无搬移但缓存差、指针开销。栈用数组尾部天然对上；队列两端操作需环形化。
head==tail 判空时，满也是 head==tail——两解：① 牺牲一格，判满 (tail+1)%n==head（容量 n-1）；② 另记 size；③ tag 位区分。Go channel 用 size 语义（qcount）。
push 进 in 栈 O(1)；pop 从 out 栈弹，out 空才把 in 全部倒入。每个元素一生最多"进 in 一次 + 倒运两次 + 出 out 一次"——总代价 O(n) 摊到 n 次操作 → 均摊 O(1)，但单次最坏 O(n)。
辅助栈与主栈同步：push 时压入 min(当前, 辅助栈顶)（每步都压，弹栈自动回滚）；或只在不大于栈顶时压（省空间但要小心重复值——用 ≤）。空间 O(n) 换时间。
计数器只数数量，查不出交错：[(]) 数量合法但非法。栈顶永远是"最近的未匹配左括号"，配对必须与最近者配——LIFO 正是嵌套语义。
每个下标至多 push 一次、pop 一次，内层 while 的总弹栈次数 ≤ n，加上外层 n 次遍历 → 总操作 ≤ 2n。和动态数组扩容同一套"总账"论证。
找"下一个更大"→ 递减栈（新的大元素来时弹出小元素给答案）；找"下一个更小"→ 递增栈。口诀：要找更大就先让小的等在栈里。84 题的"前一个更小"是递增栈从左扫。
队列保证 k 层节点先于 k+1 层被扩展——层次序即最短性来源。用栈变成 DFS，失去层次语义；无权图最短路就错了（可对照 Dijkstra 用优先队列的加权版）。
Interview QA · Part 2
同样先自答再对照。这一页的题要"结论 + 一句代价/边界"才完整——只答结论会被继续追问。
① 前缀 max 两个数组：每个柱接 min(左max,右max)−h，O(n)/O(n)；② 双指针夹逼：短边决定水位，O(n)/O(1)；③ 单调栈：按"行"结算，横向接水。三种都 O(n)，空间和思路不同。
堆要把过期元素惰性删除，每次 O(log n)；单调队列每个下标进出各一次，均摊 O(1)，且取最大直接读队头 O(1)。数据量大时差距明显。
把递归改显式栈：状态（节点+阶段）自己管理。Go 里 goroutine 栈 2KB 起自动增长、64 位默认上限 1GB，一般不爆但帧复制有成本；链表/树深度受输入控制时优先迭代。
channel = 环形缓冲（buf + sendx/recvx）+ mutex + sendq/recvq 两个等待队列。有缓冲即阻塞式生产消费队列：满则发送方挂起、接收方取走后唤醒——背压内建。字段级拆解见 channel deck。
channel/BlockingQueue 服务进程内协程/线程；Kafka 加上持久化日志、分区并行、消费组与重试回溯，服务跨机器解耦。FIFO 语义同源，规模与可靠性保证不同（Kafka deck）。
双链表（直接但指针重）、环形数组（Java ArrayDeque，取模两端推进）、块状数组（Python deque/C++ deque：块内连续 + 块间索引表）。数组系对缓存更友好。
到达序公平不再是唯一诉求时：任务有权重/截止期（调度器、Dijkstra、合并 K 链表）。堆 O(log n) 出入队换"始终取最优"——队列管顺序，堆管优先级。
Related & References
滑动窗口 →（单调队列的主战场）
回溯 →（显式栈替代递归）
Go channel 底层 →（环形缓冲 + 等待队列）
Kafka 内核 →（分布式消息队列）
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch10.1 · Stacks and Queues | 栈/队列/环形队列的形式化定义 |
| LeetCode 20/150/155/232/225/739/84/42/239 官方题解 | 单调栈/单调队列模板与复杂度论证 |
| src/runtime/chan.go（本机 Go 版本） | hchan：buf/sendx/recvx/qcount/lock/sendq/recvq |
| oi-wiki.org/basic/stack · /queue | 单调栈与单调队列的中文系统讲解 |
| docs.python.org · collections.deque | 块状双端队列实现说明 |