栈与队列：LIFO、FIFO 与循环队列
一句话定义
栈（Stack）是后进先出（LIFO）的受限线性表，只暴露 push/pop/peek；队列（Queue）是先进先出（FIFO）的受限线性表，只暴露 enqueue/dequeue；两者都是「限制访问点」从而获得 O(1) 操作与确定性行为的 ADT。
为什么重要
它们是几乎所有遍历与回退行为的引擎：函数调用栈、DFS 用栈、BFS 用队列、回溯的状态恢复用栈、消息系统用队列。限制访问点反而让行为可预测、实现极简——这是「受限即强大」的第一个范例，也是本库后续 kp-011/kp-016/kp-027 的前置引擎。
前置知识
kp-001（ADT）、kp-006（数组实现基础）。
核心概念
- 栈：操作集中在栈顶；典型应用：函数调用与递归、括号匹配、表达式求值、撤销操作、DFS、单调栈。
- 队列：插入在尾、删除在头；典型应用：BFS、任务调度、消息队列、缓冲区。
- 循环队列：数组实现队列的正确姿势——head/tail 指针对容量取模
(head+1) mod cap循环复用空间，避免「假溢出」。 - 判满/判空：牺牲一格（
(tail+1) mod cap == head为满）或额外记 size，二选一并全库一致。 - 双端队列（Deque）：两头都能进出，是栈与队列的统一实现载体。
- 单调栈：栈内元素保持单调性，O(n) 解决「下一个更大元素」类问题。
直观类比
栈是叠盘子：只能拿最上面的。队列是排队买票：先来先服务。循环队列则是「圆桌传菜」：桌子转一圈，空位循环再用，不必每次清桌。
原理与机制
数组栈：top 指向栈顶下一空位，push = a[top++]，pop = a[--top]，均摊 O(1)（扩容见 kp-004/kp-006）。循环队列：
入队: a[tail] ← x ; tail ← (tail+1) mod cap
出队: x ← a[head]; head ← (head+1) mod cap
判空: head == tail 判满: (tail+1) mod cap == head（牺牲一格）括号匹配（栈的招牌应用）：
对于 串中每个字符 c:
若 c 是左括号: push(c)
否则若 c 是右括号:
若 栈空 或 pop() 不与 c 配对: 返回 不匹配
返回 栈空
时间 Θ(n)，空间 O(n)。图示
栈: 队列: head ─▶[A][B][C][D]◀─ tail
|C| ◀栈顶 入队在尾、出队在头
|B| 循环队列（cap=6）:
|A| [F][G][ ][ ][D][E]
└── ↑head ↑tail（绕回）
出队两次后 head 越过末尾则取模回到 0，空间循环复用。实例或案例
- 函数调用栈：递归深度即栈深，
RecursionError/栈溢出就是它爆了；把递归改显式栈迭代是通用的改造手段。 - 编辑器撤销（Ctrl+Z）是栈；浏览器前进/后退是双栈。
- 消息队列（RabbitMQ/Kafka 的队列语义）是队列 ADT 在分布式的放大，削峰填谷。
- 单调栈求「每日温度：几天后更热」：每个元素至多进出栈一次，整体 O(n)。
常见误区
- 数组实现队列不取模：head 左移后前部空间永远废弃，出现「假溢出」（明明有空位却报满）。
- 忽视栈溢出：深递归在大输入上崩，应显式栈化或改迭代。
- 两栈实现队列时说「dequeue 是 O(n)」而不加均摊：倒栈摊到每个元素上是均摊 O(1)，口径要讲清（见 kp-004）。
- 混淆双端队列与栈/队列：deque 能模拟两者，但业务上仍应按语义选用以约束行为。
自测题
- 设计一个支持 push/pop/获取最小值都 O(1) 的栈，说明思路与空间代价。
答案要点：辅助同步最小栈，push 时同步压入 min(新值, 当前最小)；pop 两栈同弹；空间最坏 2n。
- 循环队列容量 6，head=4，tail=2（取模后），当前元素个数是多少？
答案要点：(tail − head + cap) mod cap = (2−4+6) mod 6 = 4。
- 用两个栈实现队列，enqueue/dequeue 的均摊复杂度各是多少？为什么是均摊？
答案要点：enqueue O(1)；dequeue 均摊 O(1)（最坏 O(n)），因为每个元素至多经历一次入栈与一次倒栈。
与其他知识点的关系
kp-011 层序遍历用队列、递归遍历依赖调用栈；kp-016 BFS/DFS 是队列/栈的图上版本；kp-027 回溯的状态恢复与撤销依赖栈语义；kp-029 的匹配过程也与括号匹配同构。
延伸阅读
《算法导论》第 10.1 节「栈和队列」；《算法（第 4 版）》第 1.3 节 Dijkstra 双栈算术表达式求值。