栈与队列 · 拾光集

环境：Windows 11 x64，GCC 13.1.0，g++ -std=c++17 -O2。耗时、输出、交叉验证结果都是本机实测。

一、栈：LIFO 的本质是”撤销”与”嵌套”

数组栈和链表栈的取舍，和上一节数组 vs 链表完全一致：

	数组栈	链表栈
push/pop	一次写 + 索引自增，无分配	每次 `new`/`delete` 一个节点
峰值内存	预留满容量	只用实际数量 + 每节点 16–24 字节
溢出	定长数组会越界（必须检查）	堆耗尽
适用	默认选择、中断/嵌入式里必须用	深度不可预测且不追求性能

std::stack 只是容器适配器（默认底层 std::deque），性能敏感时直接用 std::vector + push_back/pop_back 更好，还能随机访问栈内元素。“栈”是抽象，不必绑死某个类型。

判断该不该用栈的口诀：问题的结构是”最近打开的最先关闭”就用栈——括号匹配、表达式求值、函数调用、撤销历史、DFS、回溯、括号化输出、递归转迭代。

二、最小栈：O(1) 取最小值的做法

用一个”影子栈”只在新值 ≤ 当前最小值时压入：

struct min_stack {
    std::stack<int> s, mn;
    void push(int v) { s.push(v); if (mn.empty() || v <= mn.top()) mn.push(v); }
    void pop()       { if (s.top() == mn.top()) mn.pop(); s.pop(); }
    int  min_() const { return mn.top(); }
};

压入 5 3 8 1 4 后 min=1 top=4 size=5
弹掉栈顶 4 后 min=1
再弹掉 1 后 min=3

关键在 v <= mn.top() 里的 <=：相等时也要压，否则弹出重复的最小值后影子栈就错位了。这是这个题唯一的坑。

三、循环队列：为什么必须”少用一个槽位”

定长数组做队列，头尾下标都要回绕。问题是 head == tail 既可能是空也可能是满，无法区分。经典解法是牺牲一个槽位：

template <class T, size_t N>
struct ring_queue {
    T buf[N];
    size_t head = 0, tail = 0;
    bool empty() const { return head == tail; }
    bool full()  const { return (tail + 1) % N == head; }        /* 下一个位置是头 ⇒ 满 */
    size_t size() const { return (tail + N - head) % N; }        /* 差值取模 */
    bool push(const T &v) { if (full()) return false; buf[tail] = v; tail = (tail + 1) % N; return true; }
    bool pop(T *out)      { if (empty()) return false; *out = buf[head]; head = (head + 1) % N; return true; }
};

实测（N = 5）：

初始 empty=1 full=0 size=0
连续 push 10 次，成功 4 次；full=1 size=4
弹出并回绕写入后 size=4，依次弹出：3 100 101 102
全部弹出后 empty=1 size=0

注意两点：容量 5 只能存 4 个（这就是”少用一个位置”的代价），以及回绕后弹出的顺序依然是 FIFO（先弹剩下的 3，再弹绕回来写入的 100/101/102）。

顺手记一个我实测过的错误公式

写 size() 时很容易顺手写成 (tail + head + N) % N（我在这个探针里就写错了）。两种公式在各状态下的结果：

状态            正确size  错公式size
空(0,0)           0         0
满(0,4)           4         4
弹一个后(1,4)      3         0      ← 已经错了
回绕后(4,3)        4         2      ← 回绕后彻底失真

前两个状态碰巧对，所以单元测试只测”从 0 开始连续入队”就会漏掉它。 循环队列的测试必须包含回绕：先入队、再出队若干、再入队到绕回数组开头，然后逐项断言 size() 与弹出顺序。

（不想浪费槽位的替代方案：加一个 count 成员，或者用 head/tail + 一个 full 标志。嵌入式里常用 count 版，因为读写它天然是原子的单字操作，适合中断与主循环共享。）

四、单调栈 / 单调队列：一类题的统一套路

单调栈：维护一个”还没找到答案的元素”的候选栈，遇到破坏单调性的新元素时批量结算。适用：下一个更大元素、柱状图最大矩形、接雨水、股票跨度。

单调队列：同上，但用双端队列，还要额外做”过期元素出队”。适用：滑动窗口的最大/最小值。

滑动窗口最大值：朴素 vs 单调队列实测

20 万个随机数、窗口 500：

/* 朴素：每个窗口重扫 k 次 → O(nk) */
/* 单调队列：每个元素最多进队出队各一次 → O(n) */
while (!dq.empty() && dq.front() + k <= i) dq.pop_front();      /* 过期 */
while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();      /* 淘汰不可能赢的 */
dq.push_back(i);

朴素 O(nk) 53.8 ms | 单调队列 O(n) 2.74 ms | 结果一致=1（199501 个窗口）

19.6 倍，且窗口越大差距越夸张（k=500 时理论比是 500，实测 19.6 是因为朴素内层循环极友好地被向量化了）。注意”结果一致=1”：两种实现输出逐元素相等，这才是敢换算法的前提。

单调栈正确性怎么保证：随机数据对拍

柱状图最大矩形用单调栈是 O(n)，暴力是 O(n²)。用随机小数据把两个实现对拍：

for (int t = 0; t < 3000; t++) {
    int n = 1 + rng() % 14;                       /* 故意用短数组，暴力跑得动 */
    std::vector<int> h(n); for (auto &x : h) x = rng() % 20;
    assert(largest_rect_mono(h) == largest_rect_brute(h));
}

3000 组随机用例全部一致=1
经典例子 [2 1 5 6 2 3] → 10（教科书答案 10）

这是写算法最该养成的习惯：任何”聪明实现”都要有一个”笨实现”当参照，用随机数据比对。对拍比单测强，因为它能覆盖你想不到的边界（空、单元素、全相等、递减、含 0）。

五、双栈求中缀表达式

std::stack<long long> val;   /* 数值栈 */
std::stack<char> op;         /* 运算符栈 */
/* 数字入 val；运算符先把栈顶优先级 ≥ 自己的都算掉，再入栈；( 直接入栈；) 弹到 ( 为止 */

3+4*2            = 11  期望 11  OK
(3+4)*2          = 14  期望 14  OK
10/5-1           = 1  期望 1  OK
2*(3+4)*(5-1)    = 56  期望 56  OK

三个易错点：优先级比较要用 >=（保证左结合，10-5-1 才不会算成 6）、右括号弹到左括号为止且要把左括号丢弃、扫描数字时要 --i 回退一位（因为外层循环还会 i++）。

工程上更常见的做法是先转后缀（逆波兰）再求值，或者写递归下降解析器——递归下降比双栈更好读、更好扩展（加函数、加一元运算符都只改一处），这本身就是”用调用栈代替显式栈”的例子。

六、BFS：队列的标准用法

网格最短路径（无权图）就是 BFS，队列换成 deque 还能做 0-1 BFS：

static const int dy[4] = {-1, 1, 0, 0}, dx[4] = {0, 0, -1, 1};
std::queue<std::pair<int,int>> q;
q.push({0, 0}); dist[0][0] = 0;
while (!q.empty()) {
    auto [y, x] = q.front(); q.pop();
    for (int d = 0; d < 4; d++) {
        int ny = y + dy[d], nx = x + dx[d];
        if (in_range(ny, nx) && !visited[ny][nx]) { visited[ny][nx] = 1; dist[ny][nx] = dist[y][x] + 1; q.push({ny, nx}); }
    }
}

三条纪律：入队时就标记 visited（不是出队时，否则同一节点会被重复入队，指数爆炸）、方向数组别写错、边界判断单独成函数。

七、这一节的自查清单

栈默认用 std::vector 直接当，不必套 std::stack
定长数组做栈也要检查溢出，别假设”深度一定够”
循环队列要么少用一个槽位，要么维护 count，二选一写清楚
队列测试必须覆盖回绕后的 size() 与弹出顺序
最小栈的影子栈用 <= 压入
滑动窗口最值用单调队列，并记住”过期出队”要放在最前面
任何聪明算法都配一个暴力实现做随机对拍
BFS 在入队时标记 visited
递归转迭代时，用显式栈保存”续作状态”，别只保存局部变量

下一节讲串与模式匹配：strlen 的 O(n) 陷阱、KMP 的 next 数组怎么推、Rabin-Karp 滚动哈希，以及多模式匹配该用什么。