第 03 讲　栈及其经典应用

3.1　栈的定义与抽象数据类型

先别看代码，想一个每天都在发生的场景：食堂里一摞洗干净的盘子。阿姨把新洗好的盘子放在最上面， 同学取盘子也从最上面拿。没有谁会从中间抽一个出来 —— 一抽整摞就塌了。 这摞盘子就是一个栈 stack，它的规矩只有两条：插入和删除都只能在同一端进行，这一端叫栈顶； 另一端被封死，叫栈底。

因为只在一端操作，元素进出的顺序被强制成了后进先出（Last In First Out，LIFO）： 最后放进去的元素，一定最先被取出来；最先放进去的元素，一定最后才出来。 注意 —— 这与第 02 讲的线性表并不矛盾：栈在逻辑上仍然是线性表，只是操作被限制了。 所以我们把栈称为操作受限的线性表（restricted linear list）。限制不是缺陷，而是威力所在： 正因为只允许在一端动，栈的每一个操作都能做到 O(1)，而且「最近的未完成事项」这种信息天然被记住 —— 这正是括号匹配、递归回溯、撤销操作这些问题的共同结构。

3.1.1　五个必须背下来的术语

术语不是用来考试的装饰品，而是后面读代码时判断「这句话在说什么」的坐标。请把下面五条一次记牢。

栈 stack

限定仅在表尾进行插入和删除操作的线性表。表尾叫栈顶，表头叫栈底。逻辑结构仍是线性表，物理结构可以顺序也可以链式。

栈顶 top

允许插入和删除的那一端，是栈里唯一「活着」的位置。所有操作（Push / Pop / GetTop）都围绕它展开，因此代码里几乎每一行都有 top。

栈底 bottom

不允许操作的那一端。栈底元素是第一个入栈的元素，也只有当栈里其他元素全部弹出后，它才能出栈。

空栈 empty

不含任何元素的栈。顺序栈里通常写作 top == -1（top 指向栈顶元素下标）或 top == 0（top 指向栈顶上方空位）。判空是 Pop 与 GetTop 的第一道防线。

上溢 / 下溢

上溢 overflow：栈满时继续 Push，数组已经没有空位；下溢 underflow：栈空时继续 Pop 或 GetTop，根本没有元素可取。 上溢是空间不够，下溢是逻辑错误 —— 前者可以靠扩容或换链栈避免，后者只能靠程序员自己检查。

3.1.2　栈的 ADT 与操作集

ADT（Abstract Data Type，抽象数据类型）回答的是「这个结构能做什么」，而不回答「它怎么做到的」。 学数据结构最忌讳一上来就背数组下标 —— 先把 ADT 想清楚，你会发现顺序栈、链栈、共享栈的接口完全一样， 只是实现不同，甚至可以互相替换而调用方毫不知情。这正是抽象的价值。

用 C++ 表达这份 ADT，最自然的写法是抽象基类 + 纯虚函数。这样我们就能写出与实现无关的算法： 同一个 PrintReverse 函数，既能处理顺序栈也能处理链栈。

/* ==========================================================================
   栈的抽象数据类型（ADT）—— LIFO：后进先出
   --------------------------------------------------------------------------
   栈只允许在**同一端**（栈顶 top）进行插入和删除，这才有了「后进先出」。
   另一端叫栈底，它不动。

   竞赛里表达 ADT 不需要 class，把「运算清单」写清楚就够了：

       InitStack()      建空栈
       StackEmpty()     判空          → 空栈时 top == 0
       Push(x)          入栈（压栈）   → top 先加 1，再放 x
       Pop()            出栈（弹栈）   → 先取 a[top]，再 top 减 1
       GetTop()         取栈顶元素（不删）
       StackLength()    求栈中元素个数 → 就是 top

   两个必须分清的错误：
       上溢 overflow  —— 栈满还 push（静态数组要判；vector/链栈不用判）
       下溢 underflow —— 空栈还 pop（**这个必须判**，否则读到垃圾数据）

   说明：下面顺序栈用「top 指向栈顶元素」的约定（top = 0 表示空栈）。
   另一种常见约定是「top 指向栈顶上方空位」（top = -1 表示空栈），
   两种只差一个常数，选一种并始终用同一种，不要混。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;      // 栈的最大容量
int a[N];                  // 栈的存储区
int top = 0;               // top = 栈顶元素的下标；top == 0 表示空栈

void InitStack() { top = 0; }
bool StackEmpty() { return top == 0; }
int  StackLength() { return top; }

bool Push(int x) {         // 入栈
    if (top == N) return false;       // 上溢（静态数组才有这个问题）
    a[++top] = x;                     // 先加后写：top 从 0 变 1，写 a[1]
    return true;
}

bool Pop(int &e) {         // 出栈，用 e 带回弹出的值
    if (top == 0) return false;       // 下溢：空栈不能再弹
    e = a[top--];                     // 先取后减
    return true;
}

bool GetTop(int &e) {      // 只看不删
    if (top == 0) return false;
    e = a[top];
    return true;
}

int main() {
    InitStack();
    printf("空栈吗：%s\n", StackEmpty() ? "是" : "否");

    for (int x : {10, 20, 30, 40}) Push(x);      // 依次压入
    int e;
    GetTop(e);
    printf("栈顶 = %d，元素个数 = %d\n", e, StackLength());   // 40，4

    Pop(e);
    printf("弹出 %d\n", e);                       // 40
    Pop(e);
    printf("弹出 %d\n", e);                       // 30
    printf("现在栈顶 = ", 0);
    GetTop(e);
    printf("%d，个数 = %d\n", e, StackLength());  // 20，2

    while (!StackEmpty()) { Pop(e); printf("%d ", e); }   // 20 10（后进先出）
    printf("\n");
    printf("空栈时 Pop 返回 %d\n", (int)Pop(e));   // 0（下溢被挡住了）

    /* ---------- 复杂度 ----------
       顺序栈的 push / pop / top / 判空 全是 O(1)。
       只有「扩容」那一下是 O(n)（vector 均摊 O(1)），静态数组不存在扩容。 */
    return 0;
}

3.2　顺序栈：用数组实现

顺序栈（sequential stack）的思路朴素到不能再朴素：申请一段连续的数组空间，再用一个整型变量 top 记录栈顶在哪。 入栈就是「top 往后挪一格，把新元素写进去」，出栈就是「把 top 那格的元素交出去，top 往前挪一格」。 没有指针、没有内存分配、没有分支跳转，所以顺序栈的 Push / Pop 是常数级操作里最便宜的那种。

它还有一个经常被忽略的优势：缓存局部性 cache locality。数组元素在内存里紧挨着， 连续几次 Push 写入的是同一段缓存行，CPU 几乎不需要访问主存； 而链栈每次都要访问一个新 new 出来的结点，指针跳来跳去，常数因子明显更大。 所以在「元素个数上限能预估」的场合，顺序栈几乎总是首选。

但顺序栈有一个绕不开的问题：到底让 top 指向哪儿？不同的教材给出了两种约定，代码长得不一样， 考试里两种都会出现。你必须两种都看得懂，并且在自己的代码里始终坚持同一种 —— 混用是初学者最常见的 bug 来源。

3.2.1　top 的两种约定与它们的差别

3.2.2　SeqStack<T> 完整实现（约定 A + 动态扩容）

下面这份实现采用约定 A，并且加入了三样工程上必备的东西：动态扩容（满栈时容量翻倍而不是直接失败）、 深拷贝（拷贝构造与赋值运算符，避免两个栈共用一块内存导致 double free）、 异常保护（空栈 Pop / GetTop 抛 std::underflow_error，而不是返回垃圾值）。 代码里的 main 把入栈、取栈顶、连续出栈、下溢四种情况都跑了一遍。

/* ==========================================================================
   顺序栈 —— 数组实现（算法竞赛写法，最常用）
   --------------------------------------------------------------------------
   为什么竞赛里几乎都用顺序栈？
       · 数组访问连续，cache 友好，比链表快得多
       · 不用 new/delete，不会内存泄漏
       · 只要数组开够，就不用管扩容

   约定：top 指向**栈顶元素**，top == 0 表示空栈，元素存在 a[1..top]。
   这样判空写成 top == 0 比 top == -1 更直观，也少一个边界。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N];
int top = 0;

void InitStack()    { top = 0; }
bool StackEmpty()   { return top == 0; }
bool StackFull()    { return top == N - 1; }   // 留一个位置，或直接 top == N
int  StackLength()  { return top; }

bool Push(int x) {
    if (StackFull()) return false;
    a[++top] = x;                  // 先 ++ 再赋值
    return true;
}

bool Pop(int &e) {
    if (StackEmpty()) return false;
    e = a[top--];                  // 先取值再 --
    return true;
}

bool GetTop(int &e) {
    if (StackEmpty()) return false;
    e = a[top];
    return true;
}

void PrintStack(const char *title = "") {        // 从栈底到栈顶打印，方便看清结构
    printf("%s（栈底→栈顶）：", title);
    for (int i = 1; i <= top; ++i) printf("%d ", a[i]);
    printf("｜ top=%d\n", top);
}

int main() {
    InitStack();
    PrintStack("空栈");                          // ｜ top=0

    for (int x : {3, 1, 4, 1, 5}) Push(x);
    PrintStack("压入 3 1 4 1 5");                 // 3 1 4 1 5 ｜ top=5

    int e;
    Pop(e); Pop(e);
    PrintStack("弹出两次");                      // 3 1 4 ｜ top=3
    printf("弹掉的是 5、1（后进先出）\n");

    GetTop(e);
    printf("当前栈顶 = %d\n", e);                 // 4

    /* 演示上溢：把容量当成很小的 5 来看 */
    printf("（若 N=5，再 push 就会返回 false，这就是上溢 overflow）\n");

    /* ---------- 易错点清单 ----------
       ① 空栈 pop 必须判：否则读到的是 a[0] 里的垃圾值
       ② top 的约定要统一：这套代码里 top 是「栈顶下标」，
          如果你写的代码里 top 是「栈顶上方空位」，那 push 就是 a[top++] = x
       ③ 数组大小 N 要按题目数据范围开够，栈满会静默失败（本代码返回 false） */
    return 0;
}

3.2.3　动画：顺序栈的入栈、取栈顶与出栈

下面这个动画把「top 指针」和「数组内容」放在同一张图里同步演示：注意看每次 Push 时 top 先加一、再写值； 每次 Pop 时先把值交出来、top 再减一；以及 GetTop 只让 top 那一格闪橙色、位置完全不动。 最后一段演示的是空栈 Pop 引起的下溢。建议先点「▶ 播放」看整体节奏，再用「下一步 ▶」逐帧对照说明栏。

3.2.4　栈满、动态扩容与摊还分析

顺序栈的容量是编译期或初始化时定死的，一旦满了再 Push 就上溢。工程上有三条出路： ① 直接报错（适合容量确定、绝不该溢出的场景，如表达式求值里的运算符栈）； ② 动态扩容（容量翻倍 + 搬移，适合容量无法预估的场景，std::vector 就是这么做的）； ③ 换成链栈（根本没有「满」这个概念）。下面这份代码用约定 B 实现了一个固定容量的顺序栈， 并示范了「上溢 / 下溢用返回值报告」这种不用异常的写法 —— 请对照 3.2.1 的表格检查每一行公式。

/* ==========================================================================
   顺序栈的第二种约定：top 指向「栈顶上方的空位」
   --------------------------------------------------------------------------
   上一段用的是「top 指向栈顶元素」，所以空栈 top == 0，push 要写 a[++top] = x。
   这里换成另一种同样常见的约定：**top 指向栈顶上方那个空位**，于是：

       空栈：top == 0            栈满：top == N
       长度：就是 top            （不用再 ±1，最省事的一点）
       入栈：a[top++] = x        （先用后加）
       出栈：e = a[--top]        （先减后用）
       取栈顶：a[top - 1]        （注意要减 1！）

   两种约定的差别只在「加加减减放在哪」，算法本身完全一样。
   ★ 关键是：选定一种就一直用它，混用必出错（这是最常见的低级 bug）。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 5;                 // 故意开小一点，方便演示栈满
int a[N];
int top = 0;                     // top 指向栈顶上方空位

void InitStack() { top = 0; }
bool StackEmpty() { return top == 0; }
bool StackFull() { return top == N; }
int  StackLength() { return top; }        // 天然就是长度，不用 ±1

bool Push(int x) {
    if (StackFull()) return false;        // 上溢
    a[top++] = x;                         // 先写 a[top]，再 top++
    return true;
}

bool Pop(int &e) {
    if (StackEmpty()) return false;       // 下溢
    e = a[--top];                         // 先 --top，再取值
    return true;
}

bool GetTop(int &e) {
    if (StackEmpty()) return false;
    e = a[top - 1];                       // ★ 这里的 -1 最容易漏
    return true;
}

void PrintStack(const char *title = "") {
    printf("%s（栈底→栈顶）：", title);
    for (int i = 0; i < top; ++i) printf("%d ", a[i]);
    printf("｜ top=%d（=长度）\n", top);
}

int main() {
    InitStack();
    PrintStack("空栈");                       // ｜ top=0

    printf("依次压入 1..5：");
    for (int x = 1; x <= N; ++x) {
        bool ok = Push(x);
        printf("%d%s ", x, ok ? "✓" : "✗");
    }
    printf("\n");
    PrintStack("压满后");                     // 1 2 3 4 5 ｜ top=5

    printf("第 6 次 push 返回 %d（上溢，栈满）\n", (int)Push(6));

    int e;
    GetTop(e);
    printf("栈顶 = %d（= a[top-1] = a[4]）\n", e);   // 5

    Pop(e); Pop(e);
    printf("弹出 %d、%d\n", 5, e);            // 5、4
    PrintStack("弹两次后");                   // 1 2 3 ｜ top=3

    /* ---------- 两种约定对照表（背下来） ----------
       约定                    空栈      满栈      入栈            出栈           取栈顶
       top 指向栈顶元素        top==0    top==N-1  a[++top]=x      e=a[top--]     a[top]
       top 指向栈顶上方空位    top==0    top==N    a[top++]=x      e=a[--top]     a[top-1]
       （若把空栈定义为 top==-1，上表第一行整体平移一格，判空变成 top==-1）

       为什么很多人偏爱第二种？因为「长度 = top」不用换算，判空也最简单。
       而第一种的「取栈顶 = a[top]」更直观。选一个习惯的就行。 */
    return 0;
}

看到两种约定的代码摆在一起，你应该能体会到「约定」二字的分量：它们都对，但绝不能混。 本讲从 3.2.2 起的全部代码统一采用约定 A（top 指向栈顶元素），因为它在画图时最直观。

为什么扩容要「翻倍」而不是「加一」？

如果每次满了只加一个格子，那么连续 n 次 Push 就要搬移 1 + 2 + 3 + … + n = O(n²) 次元素， 单次操作的平均代价是 O(n)，顺序栈就退化成顺序表插入了。 改成容量翻倍后，第 k 次扩容搬移 2^k 个元素，而它能支撑接下来 2^k 次 Push， 于是总搬移量是 1 + 2 + 4 + … + 2^m ≈ 2^(m+1) < 2n， 连续 n 次 Push 的总代价是 O(n)，平均每次 O(1)。 这就是摊还分析 amortized analysis 的经典结论：

3.2.5　清空与析构：ClearStack 到底该怎么写？

顺序栈的 ClearStack 有两种写法，选哪种取决于 T 是什么：

• 写法一：top = -1;　O(1) 完成。适用于 T 是 int、double 这类「平凡类型」的情况 —— 旧值留在数组里既不影响正确性，也不占额外资源。
• 写法二：循环 Pop() 直到空　O(n)。当 T 是 std::string、含指针的类、 智能指针时，必须让每个元素的析构函数跑一遍，否则它们持有的堆内存就会泄漏。 C++ 里更地道的做法是用 std::vector<T> 当底层容器，v.clear() 会自动完成这件事。

三种实现的横向对比放在 3.4.3 节（链栈之后）一起给出，因为对比表里需要用到链栈的结论。 先把顺序栈的两条结论记住：Push / Pop / GetTop 都是 O(1)（动态扩容为摊还 O(1)）；清空是 O(1)（平凡类型）。

3.3　共享栈：两个栈共用一个数组

先看一个真实的尴尬场景：程序里需要两个栈，一个存运算符、一个存操作数， 结果运算符栈老是满（上溢），操作数栈却常年空着一大半。能不能让它们共用同一段空间、互相借？ 能 —— 这就是共享栈（也叫双栈共享空间、两栈共享存储空间）。

做法是：仍然只申请一个数组 data[0..MaxSize-1]， 但让0 号栈的栈底固定在左端、1 号栈的栈底固定在右端，两个栈顶各自向中间生长。 0 号栈入栈时 top0 右移，1 号栈入栈时 top1 左移； 只有当两个栈顶迎面撞上、中间一个空位都不剩时，才算「整个数组满了」。 也就是说，只有当一个栈占满整个数组时才会真的上溢，而这个临界点比「各自一半」远得多。

/* ==========================================================================
   共享栈 —— 两个栈共用一个数组，从两端往中间长
   --------------------------------------------------------------------------
   场景：需要两个栈，但它们的容量此消彼长（一个用得多、另一个就用得少）。
   如果各开一个定长数组，就得给两边都按最坏情况开，浪费一半空间。

   共享栈的解法：数组两端各是一个栈的栈底，两个栈顶向中间生长。
       top0 = -1 表示 0 号栈空，top0 向右长到 top0+1
       top1 = N  表示 1 号栈空，top1 向左长到 top1-1
       **栈满条件：top0 + 1 == top1**（两个栈顶挨在一起，中间没有空位）

   这样总容量 N 完全共享，只有「两个栈的总元素数」超过 N 才会上溢。
   （注意：不是各自能用到 N，而是加起来 N。）
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N];
int top0 = -1;             // 0 号栈的栈顶下标（从左往右长）
int top1 = N;              // 1 号栈的栈顶下标（从右往左长）

void InitSharedStack() { top0 = -1; top1 = N; }

bool Empty0() { return top0 == -1; }       // 0 号栈空
bool Empty1() { return top1 == N; }        // 1 号栈空
bool Full()   { return top0 + 1 == top1; } // 两个栈顶相邻 = 整个数组满了

bool Push0(int x) {        // 0 号栈入栈：向右长
    if (Full()) return false;
    a[++top0] = x;
    return true;
}
bool Push1(int x) {        // 1 号栈入栈：向左长
    if (Full()) return false;
    a[--top1] = x;
    return true;
}
bool Pop0(int &e) {
    if (Empty0()) return false;
    e = a[top0--];
    return true;
}
bool Pop1(int &e) {
    if (Empty1()) return false;
    e = a[top1++];
    return true;
}

void Dump() {              // 打印整个数组，直观看到两个栈怎么"夹"住中间
    printf("数组内容：");
    for (int i = 0; i < N; ++i) {
        if (i == 0) printf("[");
        if (i <= top0) printf("%d ", a[i]);            // 0 号栈区
        else if (i >= top1) printf("%d ", a[i]);       // 1 号栈区
        else if (i < 12) printf("· ");                 // 空闲区（只画前几个）
    }
    printf("]\n  top0=%d（0 号栈 %d 个元素）, top1=%d（1 号栈 %d 个元素）\n",
           top0, top0 + 1, top1, N - top1);
}

int main() {
    InitSharedStack();
    printf("初始：Empty0=%d Empty1=%d Full=%d\n", Empty0(), Empty1(), Full());

    for (int x : {1, 2, 3}) Push0(x);          // 0 号栈：1 2 3
    for (int x : {9, 8})    Push1(x);          // 1 号栈：9 8（9 先入，在更右边？不，1 号栈是向左长）
    Dump();

    int e;
    Pop0(e); printf("0 号栈弹出 %d\n", e);       // 3
    Pop1(e); printf("1 号栈弹出 %d\n", e);       // 8（最后压入的先出）
    Dump();

    /* 用一个小容量演示"栈满" */
    puts("\n---- 用小容量演示栈满条件 top0 + 1 == top1 ----");
    const int M = 5;
    int t0 = -1, t1 = M;
    auto full = [&] { return t0 + 1 == t1; };
    int cnt = 0;
    while (!full()) {
        ++cnt;
        if (cnt % 2) ++t0; else --t1;          // 交替往两边放
        printf("  放了 %d 个元素后：top0=%d, top1=%d, 满了吗=%d\n", cnt, t0, t1, full());
    }
    printf("  容量 %d 的数组，总共能放 %d 个元素（两个栈共用容量）\n", M, cnt);

    /* ---------- 结论 ----------
       ① 栈满条件是 top0 + 1 == top1（不是 top0 == top1）
       ② 两个栈共享容量 N，只有当它们元素总数 = N 时才溢出
       ③ 相较"各开一个定长数组"，共享栈把空间利用率提到最高，
          代价是只能用于"一个数组两个栈"这种固定场景 */
    return 0;
}

运行这段程序你会看到：8 个格子里塞进 6 个元素时仍然不算满（只剩 2 个空位，两个栈各占一半还多）， 一直要到 top0 + 1 == top1 才报上溢。这就是共享栈最实在的价值 —— 用同一块空间同时服务两个「此消彼长」的栈，把「一个撑死、一个饿死」的概率降到最低。

3.4　链栈：用单链表实现

顺序栈的容量是死的，链栈则完全跟着需求长。做法简单到一句话： 把单链表的「头」当栈顶，只在头部插入和删除。 入栈 = 头插法建表（新结点插在第一个位置），出栈 = 删除首元结点。 因为单链表在头部插入 / 删除只要改两个指针，所以 Push / Pop 都是严格 O(1)， 既不需要搬移元素，也不需要扩容，更不存在「栈满」。

为什么不能把链表尾当栈顶？因为单链表只有 next 没有 prev： 要在尾部删除，必须先从头走一遍找到倒数第二个结点，那是 O(n)。 一句话：单链表的「头」是天然的栈顶，「尾」是天然的队尾（这就是第 04 讲链队列的由来）。

3.4.1　为什么链栈通常不需要头结点，也不需要判满

这是本章最容易被问到、也最容易答错的两个「为什么」，我们分开说透。

第一，为什么可以不要头结点。头结点（dummy head）在单链表里的作用是统一「第一个位置」和「其他位置」的操作： 插入到第 1 个位置和插入到第 5 个位置都需要「修改前驱的 next」，有了头结点，第 1 个位置的前驱就是头结点， 代码不必特判。但栈永远只在头部操作，压根不存在「其他位置」，这个统一作用就用不上了。 相反，带上头结点还会带来额外负担：判空从 top == nullptr 变成 head->next == nullptr， 取栈顶要多跳一次 head->next->data，还要多 new 一个结点、在析构时多 delete 一次。 所以链栈的通行写法是不带头结点，top 直接指向首元结点，空栈就是 top == nullptr。 本节仍然先给一份带头结点的完整实现（因为很多教材和考题就是这么写的，你必须看得懂）， 再给一份不带头结点的版本，对照着看你就明白取舍在哪里。

第二，为什么不需要判满。顺序栈的「满」来自「数组下标有上限」这一物理事实。 链栈的结点是运行时用 new 从堆上要来的，只要堆还有内存就能继续 Push， 所以 StackFull() 可以永远返回 false（或者干脆不提供这个操作）。 严格地说，链栈在堆内存耗尽、new 抛 std::bad_alloc 时也会「上溢」， 但这不是数据结构层面的容量限制，而是整个进程的资源限制 —— 这时提醒用户「栈满了」没有意义， 因为程序已经处于不可恢复的状态。因此工程上链栈的 Push 只处理 bad_alloc，不做判满。

/* ==========================================================================
   链栈 —— 用单链表实现栈，只在「表头」插入和删除
   --------------------------------------------------------------------------
   为什么链栈的所有操作都是 O(1)？
   因为栈的插入删除都发生在**同一端**，我们让那一端正好是链表的表头：
       入栈 = 头插，出栈 = 删首元结点 —— 这两个都是 O(1)，不需要找前驱。
   （对比：如果让栈顶在链表尾部，出栈就得先找前驱，退化成 O(n)。）

   链栈的两个特点（考点）：
       ① 不需要判满（只要内存够就能一直 push），所以**没有上溢**
       ② 但要注意判空（空栈出栈就是下溢）
       ③ 头结点可有可无。这段代码用「带头结点」版本，插入删除的写法最统一。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head;                 // 头指针，指向头结点（哑结点）
int cnt = 0;                // 元素个数，维护它就能 O(1) 求长度

void InitStack() { head = new Node(); cnt = 0; }
bool StackEmpty() { return head->nxt == nullptr; }
int  StackLength() { return cnt; }

/* ---------- 入栈 = 头插，O(1) ----------
   新结点接上原来的首元结点，头结点再指向新结点。 */
bool Push(int x) {
    head->nxt = new Node(x, head->nxt);
    ++cnt;
    return true;                       // 链栈不会满，永远返回 true
}

/* ---------- 出栈 = 删掉首元结点，O(1) ---------- */
bool Pop(int &e) {
    if (StackEmpty()) return false;    // 下溢：空栈不能弹
    Node *p = head->nxt;               // p 就是栈顶结点
    e = p->val;
    head->nxt = p->nxt;                // 摘掉它
    delete p;                          // 竞赛里这句可以省（程序结束就回收）
    --cnt;
    return true;
}

bool GetTop(int &e) {
    if (StackEmpty()) return false;
    e = head->nxt->val;
    return true;
}

void PrintStack(const char *title = "") {     // 从栈顶到栈底打印
    printf("%s（栈顶→栈底）：", title);
    for (Node *p = head->nxt; p; p = p->nxt) printf("%d ", p->val);
    printf("｜ 个数=%d\n", cnt);
}

int main() {
    InitStack();
    printf("空栈吗：%s\n", StackEmpty() ? "是" : "否");

    for (int x : {10, 20, 30, 40}) Push(x);
    PrintStack("压入 10 20 30 40");     // 栈顶是 40

    int e;
    GetTop(e);
    printf("栈顶 = %d\n", e);           // 40
    Pop(e);
    printf("弹出 %d\n", e);             // 40
    PrintStack("弹一次后");             // 30 20 10

    printf("长度 = %d\n", StackLength());  // 3

    while (!StackEmpty()) { Pop(e); printf("%d ", e); }   // 30 20 10
    printf("\n空栈时 Pop 返回 %d\n", (int)Pop(e));         // 0

    /* ---------- 顺序栈 vs 链栈（考点） ----------
       维度           顺序栈                链栈
       时间复杂度      push/pop O(1)         push/pop O(1)
       空间           预先分配，可能浪费     按需分配，每个结点多一个指针域
       上溢           有（数组满）           没有
       是否需预分配   需要                  不需要
       缓存友好性     好（连续内存）         差（指针跳转）
       结论：能估出规模就用顺序栈；规模完全未知或很大时才用链栈。 */
    return 0;
}

/* ==========================================================================
   链栈（不带头结点版）—— 少一个哑结点，边界要自己判
   --------------------------------------------------------------------------
   带头结点的链栈，空栈时 head->nxt == NULL，push/pop 的写法统一；
   不带头结点时，head 直接指向**栈顶元素**，空栈就是 head == NULL。

   不带头结点的代价：push 时必须特判"栈原来是空的"，
   因为要把 head 从 NULL 改成新结点，而这一步和"往非空栈里 push"不一样。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *nxt;
    Node(int v = 0, Node *p = nullptr) : val(v), nxt(p) {}
};

Node *head = nullptr;        // 直接指向栈顶元素；NULL 表示空栈
int cnt = 0;

void InitStack() { head = nullptr; cnt = 0; }
bool StackEmpty() { return head == nullptr; }
int  StackLength() { return cnt; }

/* ---------- 入栈：两种写法，第二种更简洁 ---------- */
bool Push(int x) {
    // 写法一：特判空栈
    // if (head == nullptr) { head = new Node(x); ++cnt; return true; }
    // head->nxt = new Node(x, head->nxt);   // 新结点插在栈顶后面
    // ++cnt; return true;

    // 写法二：构造新结点时直接让它指向旧栈顶，再让 head 指向它（空栈时也成立）
    head = new Node(x, head);            // 空栈时 head 是 nullptr，new 的结点 nxt 也就是 nullptr ✓
    ++cnt;
    return true;
}

/* ---------- 出栈：必须特判，因为摘掉栈顶后 head 要指向下一个，可能是 NULL ---------- */
bool Pop(int &e) {
    if (StackEmpty()) return false;
    Node *p = head;
    e = p->val;
    head = p->nxt;                       // head 直接后移（空栈时自然变成 nullptr）
    delete p;
    --cnt;
    return true;
}

bool GetTop(int &e) {
    if (StackEmpty()) return false;
    e = head->val;                       // 不带头结点时，栈顶就是 head 自己
    return true;
}

void PrintStack(const char *title = "") {
    printf("%s（栈顶→栈底）：", title);
    for (Node *p = head; p; p = p->nxt) printf("%d ", p->val);
    printf("｜ 个数=%d\n", cnt);
}

int main() {
    InitStack();
    printf("空栈吗：%s\n", StackEmpty() ? "是" : "否");

    Push(1); Push(2); Push(3);
    PrintStack("压入 1 2 3");             // 3 2 1
    int e;
    GetTop(e);
    printf("栈顶 = %d（就是 head 自己指向的结点）\n", e);   // 3

    Pop(e); Pop(e);
    PrintStack("弹两次后");              // 1
    Pop(e);
    printf("弹掉最后一个后，head = %s\n", head == nullptr ? "NULL" : "非空");
    printf("空栈再 Pop 返回 %d\n", (int)Pop(e));            // 0

    /* ---------- 两种链栈对比 ----------
       带头结点：push/pop 不用特判，代码统一；多占一个结点空间
       不带头结点：省一个结点，但 push/pop 都要考虑"空"这个边界
       竞赛选择：写链表时统一用带头结点，能少写一堆 if。 */
    return 0;
}

3.4.2　顺序栈 vs 链栈：一张表说清所有取舍

// stl_stack_demo.cpp —— 标准库的 std::stack：容器适配器，底层默认是 std::deque
// 记住三点：① 它只是「适配器」，不提供迭代器，不能遍历；
//          ② 默认底层 deque 可以换：stack<int, vector<int>> 就是用 vector 存；
//          ③ 接口是 push / pop / top / empty / size，pop() 不返回值（要自己先取 top）。
#include <iostream>
#include <stack>
#include <vector>
#include <string>

int main() {
    std::stack<int> s;                       // 底层 std::deque<int>
    for (int v : {12, 7, 25}) s.push(v);
    std::cout << "size = " << s.size() << "，top = " << s.top() << '\n';
    s.top() = 99;                             // top() 返回引用，可以直接改栈顶
    while (!s.empty()) { std::cout << s.top() << ' '; s.pop(); }
    std::cout << '\n';

    std::stack<int, std::vector<int>> sv;    // 换成 vector 做底层容器
    for (int v : {1, 2, 3}) sv.push(v);
    std::cout << "vector 版 top = " << sv.top() << '\n';

    std::stack<std::string> st;              // 元素类型任意
    st.push("出"); st.push("先"); st.push("进"); st.push("后");
    while (!st.empty()) { std::cout << st.top(); st.pop(); }
    std::cout << "　← 出栈顺序恰好是入栈顺序的逆序\n";
    return 0;
}

3.5　经典应用一：括号匹配

编译器在你少写一个右括号时会准确报出「括号不匹配」，检查器（linter）能一眼看出 ([)] 是错的。 它们用的算法，核心就是这一个栈。这个例子之所以经典，是因为它把栈的本质暴露得最彻底： 「最近的、还没有被处理完的东西」永远在栈顶。

3.5.1　本质：右括号要找「最近的」左括号

从左到右扫描字符串，遇到左括号就意味着「欠了一笔账」，先记账； 遇到右括号就是「来还账」，它必须和最近一笔还没还的账抵消。 而「最近的未完成事项」正好就是栈顶 —— 这就是为什么必须用栈，而不能用队列： 队列是先进先出，还的会是最早的那笔账，嵌套结构立刻就错了。

算法描述只有五行：

1. 遇到左括号 ( [ {：入栈。
2. 遇到右括号 ) ] }：若栈空，说明这个右括号多余，失败；
3. 否则看栈顶：与当前右括号类型相同则弹出（配对成功），类型不同则失败。
4. 扫描结束后再检查栈：栈空 → 匹配成功；栈非空 → 有左括号没被配对，失败。
5. 其它字符（字母、数字、运算符、空白）一律跳过 —— 括号匹配只关心括号。

3.5.2　三种失败情形

下面这个动画把四种情况连在一起演示：{[()]} 匹配成功，([)] 类型不匹配， (() 左括号多余，()) 右括号多余。每换一个串，动画都会重新开始扫描， 注意观察橙色指针（当前字符）与栈内容的变化。

3.5.3　C++ 完整实现

第一份实现是「工程版」：返回失败原因和精确位置，方便直接集成到编译器的报错信息里。 第二份是「考试版」：只返回 bool，十几行手写就能默出来。两份都值得会。

// bracket_match.cpp —— 括号匹配（工程版）：支持 () [] {}，返回失败位置与原因
#include <iostream>
#include <string>
#include <stack>
#include <utility>

// 返回空串表示匹配成功；否则返回人类可读的失败原因
std::string CheckBrackets(const std::string& s) {
    std::stack<std::pair<char, int> > st;      // 存 (左括号, 它的下标)
    for (int i = 0; i < (int)s.size(); ++i) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            st.push(std::make_pair(c, i));                      // 记账
        } else if (c == ')' || c == ']' || c == '}') {
            char want = (c == ')') ? '(' : (c == ']' ? '[' : '{');
            if (st.empty())
                return "位置 " + std::to_string(i) + " 的 '" + c + "' 多余：右括号多余";
            if (st.top().first != want)
                return "位置 " + std::to_string(i) + " 的 '" + c + "' 与位置 " +
                       std::to_string(st.top().second) + " 的 '" + st.top().first + "' 类型不匹配";
            st.pop();                                           // 销账
        }
        // 其它字符（字母 / 数字 / 运算符 / 空格）一律跳过
    }
    if (!st.empty())
        return "位置 " + std::to_string(st.top().second) + " 的 '" + st.top().first + "' 多余：左括号多余";
    return "";
}

void Test(const std::string& s) {
    std::string r = CheckBrackets(s);
    std::cout << (r.empty() ? "[通过] " : "[失败] ") << '"' << s << '"';
    if (!r.empty()) std::cout << "   → " << r;
    std::cout << '\n';
}

int main() {
    Test("{[()]}");
    Test("((1+2)*[3-4])/5");
    Test("([)]");                 // 类型不匹配
    Test("(()");                  // 左括号多余
    Test("())");                  // 右括号多余
    Test("");                     // 空串算匹配
    Test("no brackets at all");   // 没有括号也算匹配
    return 0;
}

// bracket_match_simple.cpp —— 括号匹配（考试版）：只判断是否匹配，手写十几行
#include <iostream>
#include <stack>

bool Match(const char* str) {
    std::stack<char> st;
    for (const char* p = str; *p; ++p) {
        char c = *p;
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);                                   // 左括号入栈
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;                 // 情形一：右括号多余
            char t = st.top();
            st.pop();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;     // 情形三：类型不匹配
        }
    }
    return st.empty();                                    // 情形二：栈非空 = 左括号多余
}

int main() {
    const char* cases[] = {"{[()]}", "([)]", "(()", "())", "a*(b+[c-d])"};
    for (const char* s : cases)
        std::cout << (Match(s) ? "匹配   " : "不匹配 ") << s << '\n';
    return 0;
}

3.6　经典应用二：进制转换

十进制转其他进制用的是小学就学过的短除法：不断用 N 除以基数 base， 记下余数，直到商为 0，最后把余数从下往上读出来，就是结果。 问题在于：人可以用眼睛「从下往上」读，程序里怎么做到？

关键在于推一遍公式。任何一个 base 进制数都可以写成：

也就是说，第一次除出来的余数 d_0 是最低位，最后一次除出来的 d_k 才是最高位。 而输出时必须先输出 d_k、最后输出 d_0 —— 这正是「先进后出」。 于是：算出来的余数依次入栈，算完之后依次出栈输出，顺序天然被倒过来了。 除了栈，你也可以用数组存下来再倒着遍历（本质一样），或者用递归（本质还是栈）。

手动验算 156 = 10011100₂：1×2⁷ + 0×2⁶ + 0×2⁵ + 1×2⁴ + 1×2³ + 1×2² + 0×2¹ + 0×2⁰ = 128 + 16 + 8 + 4 = 156 ✓。

下面这个动画把「短除法竖式」和「余数栈」并排放在一起：左边每算一步就多一行除法， 右边对应地多压一个余数；除法结束后商变成 0，再从左到右逐个出栈，结果字符串就一点点拼出来了。 请特别注意入栈的是余数、出栈顺序才是最终答案这一点。

// base_convert.cpp —— 十进制转 2~16 任意进制（含负数、0 与非法进制处理）
#include <iostream>
#include <string>
#include <stack>
#include <stdexcept>

std::string ToBase(long long n, int base) {
    if (base < 2 || base > 16)
        throw std::invalid_argument("进制必须在 2~16 之间");

    const char* DIGIT = "0123456789ABCDEF";
    bool neg = (n < 0);
    // 取绝对值：先 -(n+1) 再 +1，避免 n == LLONG_MIN 时取负溢出
    unsigned long long x = neg ? (static_cast<unsigned long long>(-(n + 1)) + 1ULL)
                               : static_cast<unsigned long long>(n);

    std::stack<char> st;                       // 用栈保存余数
    if (x == 0) st.push('0');                  // 0 要特判，否则循环一次都不执行
    while (x > 0) {
        st.push(DIGIT[x % base]);              // 低位先入栈
        x /= base;
    }

    std::string out;
    if (neg) out += '-';
    while (!st.empty()) {                      // 出栈 = 高位 → 低位
        out += st.top();
        st.pop();
    }
    return out;
}

int main() {
    long long tests[] = {156, 0, 255, -156, 1000000000LL};
    for (long long v : tests) {
        std::cout << v << " → 二进制 " << ToBase(v, 2)
                  << " | 八进制 " << ToBase(v, 8)
                  << " | 十六进制 " << ToBase(v, 16) << '\n';
    }
    try { ToBase(10, 20); }
    catch (const std::exception& e) { std::cout << "非法进制 → " << e.what() << '\n'; }
    return 0;
}

3.7　经典应用三：表达式求值（本章重头戏）

「计算 3 + 4 * 2 - ( 1 + 5 ) ^ 2 / 3」对人来说是一眼的事，对计算机却是一整套栈的配合。 这一节我们分四步走：先搞清楚三种表达式长什么样、怎么手推互转； 再给出中缀转后缀的完整规则表；然后写三份 C++ 代码（中缀转后缀、后缀求值、中缀直接求值）； 最后解释为什么编译器偏爱后缀表达式。这一节内容多，但它是整门课里「栈」这个工具最漂亮的一次表演。

3.7.1　中缀、前缀、后缀：三种表达式

我们平时写的算术式叫中缀表达式（infix expression）：运算符放在两个操作数中间， 再靠括号和优先级来规定运算顺序。它的优点是符合人类直觉，缺点是对机器极不友好： 计算机必须来回扫描找到优先级最高的那一步，还要处理括号的嵌套。

如果把运算符挪到操作数前面，就得到前缀表达式（prefix expression）， 也叫波兰式（Polish notation，得名于波兰数学家 Jan Łukasiewicz）； 挪到后面就是后缀表达式（postfix expression），也叫逆波兰式（Reverse Polish Notation，RPN）。 三种写法里操作数的相对顺序完全一样，变的只是运算符的位置 —— 这一点务必先记住， 它是所有转换方法的基础。

为什么这三种写法能表达同一个式子？因为一个表达式本质上是一棵表达式树（expression tree）： 操作数在叶子上，运算符在内部结点上。对这棵树做前序遍历得到前缀表达式， 做后序遍历得到后缀表达式，做中序遍历得到中缀表达式（但会丢掉括号，所以严格说需要重新加括号）。 理解了这一点，「三种表达式互转」就退化成了「树的三种遍历」—— 这是本章与第 07 讲（树与二叉树）之间的一座桥。

手推方法一：加括号法（最快，考试首选）

步骤如下：① 按优先级与结合性，给每一处运算都加上一对括号，直到整个式子被一个最外层括号包住； ② 把每个运算符移到它所对应的那对括号的「外面」——移到右括号后面就得到后缀，移到左括号前面就得到前缀； ③ 去掉所有括号。

用一个更小的例子验证这个方法的正确性：1 + 2 * 3 → 加括号 ( 1 + ( 2 * 3 ) ) → 后缀 1 2 3 * +、前缀 + 1 * 2 3。心算一下：后缀扫描时先算 2 3 * 得 6，再算 1 6 + 得 7 ✓ —— 括号的位置恰好规定了「谁先结合」，所以后缀式里再写括号就是多余的。

手推方法二：栈扫描法（程序实现的方法）

把上面的过程「机械化」，就是接下来要讲的算法。下面是中缀转后缀的逐步推导表， 和 3.7.3 节动画里演的完全是同一件事。建议你先自己在纸上推一遍，再用动画对答案。

3.7.2　中缀转后缀：完整规则与优先级表

算法的骨架只有四句话，难点全在「优先级怎么定」。先给结论表：

为什么左结合的运算符要满足 icp = isp − 1？因为「弹出条件」是 isp(栈顶) >= icp(当前)：当两者同级时（比如栈顶是 +、当前也是 +）， 3 >= 2 成立，于是先入栈的那个先弹出 —— 这正是左结合的语义（a-b-c 要算成 (a-b)-c）。 而 ^ 是右结合的（a^b^c = a^(b^c)），所以要让同级时不弹， 只能把关系反过来：icp = isp + 1，这样 6 >= 7 不成立，栈顶的 ^ 就留住了。

3.7.3　中缀转后缀的 C++ 实现

下面这个动画是本节的核心：它把「输入指针、运算符栈、输出序列」三者放在同一屏里同步推进。 每一帧的说明栏都会写出 isp 与 icp 的具体比较过程，你可以一格一格地对着 3.7.2 的表格看。 特别注意第 6 步（遇到 - 时连弹两个运算符）、第 11 步（遇到 ) 时弹到左括号）和最后一步（扫描完还要清栈）。

// infix_to_postfix.cpp —— 中缀表达式转后缀表达式
// 支持：多位数、小数、+ - * / ^ 与圆括号；^ 为右结合（icp > isp）
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cctype>
#include <stdexcept>

/* 栈内优先级：运算符已经在栈里时的优先级 */
int Isp(char op) {
    switch (op) {
        case '+': case '-': return 3;
        case '*': case '/': return 5;
        case '^':           return 6;      // 右结合：栈内比栈外小 1
        case '(':           return 1;      // 最低：谁也弹不走它
        default:            return -1;
    }
}
/* 栈外优先级：运算符还没进栈时的优先级 */
int Icp(char op) {
    switch (op) {
        case '+': case '-': return 2;
        case '*': case '/': return 4;
        case '^':           return 7;      // 右结合：等优先级时不弹，先入栈
        case '(':           return 6;      // 最高：一进栈就压住下面的运算符
        default:            return -1;
    }
}

/* 把字符串切成 token：连续的数字与小数点算一个操作数，其余每个字符算一个运算符 */
std::vector<std::string> Tokenize(const std::string& s) {
    std::vector<std::string> out;
    for (size_t i = 0; i < s.size(); ) {
        char c = s[i];
        if (isspace(static_cast<unsigned char>(c))) { ++i; continue; }
        if (isdigit(static_cast<unsigned char>(c)) || c == '.') {
            std::string num;
            while (i < s.size() && (isdigit(static_cast<unsigned char>(s[i])) || s[i] == '.'))
                num += s[i++];
            out.push_back(num);
        } else {
            out.push_back(std::string(1, c));
            ++i;
        }
    }
    return out;
}
bool IsNumber(const std::string& t) {
    return !t.empty() && (isdigit(static_cast<unsigned char>(t[0])) || t[0] == '.');
}

std::string InfixToPostfix(const std::string& expr) {
    std::vector<std::string> tk = Tokenize(expr);
    std::stack<char> ops;                     // 运算符栈
    std::string out;                          // 输出序列（后缀式）

    for (size_t i = 0; i < tk.size(); ++i) {
        const std::string& t = tk[i];
        if (IsNumber(t)) {                    // ① 操作数：直接输出
            out += t; out += ' ';
        } else if (t == "(") {                // ② 左括号：直接入栈
            ops.push('(');
        } else if (t == ")") {                // ③ 右括号：弹到左括号为止
            if (ops.empty()) throw std::runtime_error("括号不匹配：多余的 )");
            while (!ops.empty() && ops.top() != '(') { out += ops.top(); out += ' '; ops.pop(); }
            ops.pop();                        // 左括号出栈丢弃，不输出
        } else {                              // ④ 运算符：先弹后压
            char op = t[0];
            if (Icp(op) < 0) throw std::runtime_error(std::string("非法字符：") + op);
            while (!ops.empty() && Isp(ops.top()) >= Icp(op)) {
                out += ops.top(); out += ' '; ops.pop();
            }
            ops.push(op);
        }
    }
    while (!ops.empty()) {                    // ⑤ 收尾：清空运算符栈
        if (ops.top() == '(') throw std::runtime_error("括号不匹配：多余的 (");
        out += ops.top(); out += ' '; ops.pop();
    }
    if (!out.empty() && out.back() == ' ') out.pop_back();
    return out;
}

int main() {
    const char* tests[] = {
        "3 + 4 * 2 - ( 1 + 5 ) ^ 2 / 3",       // 本节主线例子
        "2 ^ 3 ^ 2",                           // 右结合：必须是 2 3 2 ^ ^
        "1.5 + 22 * ( 3 - 0.5 )",              // 多位数与小数
        "( 1 + 2 ) * 3 - 4 / 2",
        "8 - 4 - 2",                           // 左结合：必须是 8 4 - 2 -
        "7"
    };
    for (const char* s : tests) {
        std::cout << s << "\n   → " << InfixToPostfix(s) << "\n";
    }
    try { InfixToPostfix("( 1 + 2"); }
    catch (const std::exception& e) { std::cout << "错误捕获 → " << e.what() << '\n'; }
    return 0;
}

3.7.4　后缀表达式求值

后缀求值比中缀转后缀还简单，规则一句话：从左到右扫描，遇操作数就压栈， 遇运算符就弹出两个操作数、算完把结果压回去。扫描结束时栈里恰好剩下一个数，那就是答案。 整个过程不需要知道优先级，也不需要处理括号 —— 因为后缀式里本来就没有括号。

手推一遍主线例子 3 4 2 * + 1 5 + 2 ^ 3 / -：

中缀验算：3 + 4×2 = 11，(1+5)² ÷ 3 = 36 ÷ 3 = 12，11 − 12 = −1 ✓ 完全一致。

// postfix_eval.cpp —— 后缀表达式求值：一个操作数栈 + 一次线性扫描
// 支持多位数（如 22、100）与小数（如 1.5、0.25）
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <stdexcept>

std::vector<std::string> Tokenize(const std::string& s) {
    std::vector<std::string> out;
    for (size_t i = 0; i < s.size(); ) {
        char c = s[i];
        if (isspace(static_cast<unsigned char>(c))) { ++i; continue; }
        if (isdigit(static_cast<unsigned char>(c)) || c == '.') {
            std::string num;
            while (i < s.size() && (isdigit(static_cast<unsigned char>(s[i])) || s[i] == '.'))
                num += s[i++];
            out.push_back(num);
        } else {
            out.push_back(std::string(1, c));
            ++i;
        }
    }
    return out;
}
bool IsNumber(const std::string& t) {
    return !t.empty() && (isdigit(static_cast<unsigned char>(t[0])) || t[0] == '.');
}

double EvalPostfix(const std::string& expr) {
    std::vector<std::string> tk = Tokenize(expr);
    std::stack<double> st;                    // 操作数栈
    for (size_t i = 0; i < tk.size(); ++i) {
        const std::string& t = tk[i];
        if (IsNumber(t)) {
            st.push(std::stod(t));            // 多位数 / 小数一次读入
            continue;
        }
        if (st.size() < 2) throw std::runtime_error("后缀式非法：操作数不足");
        double b = st.top(); st.pop();        // ★ 先弹出的是右操作数
        double a = st.top(); st.pop();        // ★ 后弹出的是左操作数
        double v = 0;
        switch (t[0]) {
            case '+': v = a + b; break;
            case '-': v = a - b; break;
            case '*': v = a * b; break;
            case '/':
                if (b == 0) throw std::runtime_error("除数为 0");
                v = a / b; break;
            case '^': v = std::pow(a, b); break;
            default:  throw std::runtime_error("非法运算符：" + t);
        }
        st.push(v);                           // 结果压回栈中
    }
    if (st.size() != 1) throw std::runtime_error("后缀式非法：扫描结束栈中元素个数不为 1");
    return st.top();
}

int main() {
    const char* tests[] = {
        "3 4 2 * + 1 5 + 2 ^ 3 / -",          // = -1
        "1.5 22 3 0.5 - * +",                 // = 56.5
        "2 3 2 ^ ^",                          // = 512（右结合）
        "100 25 /",                           // = 4（多位数）
        "8 4 - 2 -",                          // = 2（左结合）
        "3 4 -"                               // = -1（谁减谁）
    };
    for (const char* s : tests) {
        std::printf("%-28s = %g\n", s, EvalPostfix(s));
    }
    try { EvalPostfix("1 +"); }
    catch (const std::exception& e) { std::cout << "错误捕获 → " << e.what() << '\n'; }
    return 0;
}

3.7.5　中缀表达式直接求值：双栈法

现实中我们往往拿到的就是中缀表达式，于是有两种工程路线： ① 先转后缀，再求值（两遍扫描，逻辑最清晰，编译器就是这么做的）； ② 一遍扫描直接求值（双栈法：一个操作数栈 + 一个运算符栈）。 双栈法的做法与「转后缀」几乎一模一样，唯一的区别是：每当一个运算符应当「输出」时， 就地用操作数栈把它算掉，而不是写到输出串里。

/* ==========================================================================
   中缀表达式直接求值 —— 双栈法（操作数栈 + 运算符栈）
   --------------------------------------------------------------------------
   前面两段是"先转后缀再求值"，这段是不转换、边扫边算的双栈做法。
   两种做法的复杂度一样（都是 O(n)），但双栈法更短，竞赛里常用。

   规则（就三条）：
     ① 遇到数字      → 压入「操作数栈」
     ② 遇到左括号    → 压入「运算符栈」
     ③ 遇到右括号    → 一直弹出运算符来计算，直到弹出左括号为止
     ④ 遇到运算符    → 只要栈顶运算符的优先级 ≥ 当前运算符，就先弹出来算掉，
                        再把当前运算符压栈（**注意同级也要先算**，保证从左到右结合）
     ⑤ 扫描结束      → 把运算符栈里剩下的全部弹出来算完
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int numStk[N];  int numTop = 0;          // 操作数栈
char opStk[N];  int opTop = 0;           // 运算符栈

void Init() { numTop = opTop = 0; }

void pushNum(int x) { numStk[++numTop] = x; }
int  popNum()       { return numStk[numTop--]; }
void pushOp(char c) { opStk[++opTop] = c; }
char popOp()        { return opStk[opTop--]; }
char topOp()        { return opTop ? opStk[opTop] : '#'; }

int priority(char c) {                   // 数字越大越优先
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    return 0;                            // 括号和 '#' 不给优先级
}

/* 弹出一个运算符，从操作数栈取两个数算完再压回去。
   注意顺序：先弹出的是**右操作数**，后弹出的是**左操作数**！
   减法和除法搞反了结果就全错。 */
void calcOnce() {
    char op = popOp();
    int  b = popNum();                    // 右操作数
    int  a = popNum();                    // 左操作数
    int  r = 0;
    if (op == '+') r = a + b;
    else if (op == '-') r = a - b;
    else if (op == '*') r = a * b;
    else r = a / b;
    pushNum(r);
}

int evalInfix(const string &s) {
    Init();
    int i = 0, n = s.size();
    while (i < n) {
        char c = s[i];
        if (c == ' ') { ++i; continue; }

        if (isdigit(c)) {                  // ① 数字：可能有多位，要读完整个数
            int x = 0;
            while (i < n && isdigit(s[i])) { x = x * 10 + (s[i] - '0'); ++i; }
            pushNum(x);
            continue;
        }
        if (c == '(') { pushOp(c); ++i; continue; }        // ② 左括号直接压
        if (c == ')') {                                    // ③ 右括号：算到左括号
            while (topOp() != '(') calcOnce();
            popOp();                                       // 把左括号弹掉（不参与计算）
            ++i;
            continue;
        }
        /* ④ 运算符：栈顶优先级 ≥ 当前就先算，再把当前压栈 */
        while (opTop && priority(topOp()) >= priority(c)) calcOnce();
        pushOp(c);
        ++i;
    }
    while (opTop) calcOnce();              // ⑤ 收尾：把剩下的运算符全算掉
    return numStk[numTop];
}

/* ---------- 为了对照，再给一份"先转后缀再求值"的分步版本 ---------- */
string toPostfix(const string &s) {
    Init();
    string out = "";
    int i = 0, n = s.size();
    while (i < n) {
        char c = s[i];
        if (c == ' ') { ++i; continue; }
        if (isdigit(c)) {
            while (i < n && isdigit(s[i])) out += s[i++];
            out += ' ';
            continue;
        }
        if (c == '(') { pushOp(c); ++i; continue; }
        if (c == ')') {
            while (topOp() != '(') { out += popOp(); out += ' '; }
            popOp();
            ++i;
            continue;
        }
        while (opTop && priority(topOp()) >= priority(c)) { out += popOp(); out += ' '; }
        pushOp(c);
        ++i;
    }
    while (opTop) { out += popOp(); out += ' '; }
    return out;
}

int evalPostfix(const string &pf) {
    Init();
    stringstream ss(pf);
    string tk;
    while (ss >> tk) {
        if (isdigit(tk[0])) { pushNum(stoi(tk)); continue; }
        char op = tk[0];
        int b = popNum(), a = popNum();
        int r = (op == '+') ? a + b : (op == '-') ? a - b : (op == '*') ? a * b : a / b;
        pushNum(r);
    }
    return numStk[numTop];
}

int main() {
    string e = "3 + 4 * 2 - ( 1 + 5 ) * 3";
    printf("中缀表达式：%s\n", e.c_str());
    printf("双栈直接求值     = %d\n", evalInfix(e));            // 3+8-18 = -7

    string pf = toPostfix(e);
    printf("转成后缀         = %s\n", pf.c_str());              // 3 4 2 * + 1 5 + 3 * -
    printf("按后缀求值       = %d\n", evalPostfix(pf));          // -7（两种做法结果一致）

    /* 再验几个易错例子 */
    printf("10 - 3 - 2 = %d（左结合，不是 10-(3-2)=9）\n", evalInfix("10 - 3 - 2"));   // 5
    printf("2 + 3 * 4 = %d（先乘后加）\n", evalInfix("2 + 3 * 4"));                    // 14
    printf("(2 + 3) * 4 = %d（括号优先）\n", evalInfix("( 2 + 3 ) * 4"));              // 20
    printf("100 / 5 / 2 = %d（左结合，不是 100/(5/2)=40）\n", evalInfix("100 / 5 / 2")); // 10

    /* ---------- 易错点 ----------
       ① 弹操作数时的顺序：先弹出的是右操作数（b），后弹出的是左操作数（a）
       ② 同级运算符也要先算栈顶的（保证左结合），所以判断是 >= 而不是 >
       ③ 多位数字要一次读完，不能一位一位压栈
       ④ 右括号处理完后，左括号要弹掉但不能参与计算 */
    return 0;
}

3.7.6　为什么计算机喜欢后缀表达式

学到这里你应该已经体会到：中缀式是给人看的，后缀式是给机器算的。具体理由有五条：

1. 不需要括号。后缀式中运算符的位置已经唯一确定了运算顺序，括号纯属多余。省掉括号，就省掉了「括号嵌套」这一整类复杂度。
2. 不需要优先级表。求值过程里没有任何一次「比较优先级」的判断 —— 后端的求值器可以完全不懂 * 比 + 优先级高这件事。
3. 一次线性扫描，一个栈。每个 token 只处理一次，总共 O(n) 时间、O(n) 空间，实现只有十几行，出错概率极低。
4. 求值顺序天然确定。后缀式规定了严格从左到右的运算次序，不存在歧义，非常适合翻译成「栈式机器」的指令序列 —— JVM 字节码、.NET IL、PostScript、Forth 都是这种栈式指令集；HP 科学计算器至今仍用 RPN 输入。
5. 易于生成。语法分析器在自底向上归约时，天然就是「先处理子表达式、再处理父表达式」的顺序， 直接输出就是后缀式；三元式、四元式（三地址码）与它一脉相承。

代价也很明显：人读后缀式很痛苦。所以调试编译器时，工程师经常要把中间代码「反着打印成中缀式」来看。 这也是为什么三种表达式都要会：中缀负责让人看懂，前缀 / 后缀负责让机器算得快。

3.8　栈与递归：为什么递归能「自动回溯」

很多人学递归时的困惑是：「函数调用自己，怎么就自己回来了？」答案就藏在这句话里 —— 递归之所以能自动回溯，是因为系统在背后替你维护了一个栈。 你写的每一层递归调用，都会在内存里留下一个栈帧（stack frame，也叫活动记录 activation record）， 函数返回时，系统从栈帧里恢复现场，于是「回到调用点继续往下执行」。这一节我们把这件事拆开看。

3.8.1　函数调用栈与栈帧

程序里的函数调用栈（call stack）是操作系统与编译器共同维护的一个栈。每次调用一个函数，就入栈一个栈帧； 函数返回，就出栈并销毁它。一个栈帧里通常存着四样东西：

• 返回地址：函数执行完后要跳回哪一行继续执行（这一条最关键 —— 它就是「回溯」的锚点）。
• 参数与局部变量：本次调用的 n、left、i 等等。
• 调用者的寄存器现场：保证返回后调用者的计算能继续。
• 临时保存的中间结果：比如 n * f(n-1) 里已经算好的 n。

因为每层调用都有自己独立的栈帧，所以 每一层的 n 互不干扰 —— 这就是递归能正确处理 f(4) 里那个 n = 4、f(3) 里那个 n = 3 的原因。 同一时刻栈里最多有多少个栈帧，就是递归深度，也就是递归的空间复杂度。 深度太大（比如十万层）就会把这块固定大小的栈空间撑爆，报出那个著名的 stack overflow（栈溢出）—— 注意这里的「栈」不是我们讲的抽象数据结构，而是系统调用栈； 但它的原理完全一样：后进先出，超出容量就上溢。

3.8.2　三个经典递归：阶乘、斐波那契、汉诺塔

// recursion_demo.cpp —— 阶乘 / 斐波那契 / 汉诺塔：递归的三种典型形状
#include <iostream>
#include <vector>

/* ① 阶乘：线性递归。递归深度 = n，每层都要等下一层的结果才能相乘 */
long long FactRec(int n) {
    if (n <= 1) return 1;                 // 递归出口（base case）
    return n * FactRec(n - 1);            // 递推关系：n! = n × (n−1)!
}
long long FactIter(int n) {               // 迭代版：自底向上，不需要栈
    long long r = 1;
    for (int i = 2; i <= n; ++i) r *= i;
    return r;
}

/* ② 斐波那契：树形递归。朴素写法会重复计算大量子问题，复杂度 O(2^n) */
long long FibRec(int n) {
    return n < 2 ? n : FibRec(n - 1) + FibRec(n - 2);
}
/* 记忆化搜索：把算过的答案存下来，每个状态只算一次 → O(n)，是动态规划的雏形 */
long long FibMemo(int n, std::vector<long long>& memo) {
    if (n < 2) return n;
    if (memo[n] != -1) return memo[n];                 // 已经算过，直接取
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}

/* ③ 汉诺塔：把「搬 n 个」拆成「搬 n−1 个 → 搬 1 个 → 搬 n−1 个」，移动次数 = 2^n − 1 */
long long hanoiMoves = 0;
void Hanoi(int n, char from, char via, char to) {
    if (n == 1) {
        ++hanoiMoves;
        if (hanoiMoves <= 7)
            std::cout << "  第 " << hanoiMoves << " 步：把盘子 1 从 " << from << " 移到 " << to << '\n';
        return;
    }
    Hanoi(n - 1, from, to, via);          // ① 把上面 n−1 个挪到中转柱
    ++hanoiMoves;                          // ② 最大的那个盘子直接搬到目标柱
    if (hanoiMoves <= 7)
        std::cout << "  第 " << hanoiMoves << " 步：把盘子 " << n << " 从 " << from << " 移到 " << to << '\n';
    Hanoi(n - 1, via, from, to);          // ③ 再把 n−1 个从中转柱挪到目标柱
}

int main() {
    std::cout << "5! 递归 = " << FactRec(5) << "，迭代 = " << FactIter(5) << '\n';
    std::cout << "Fib(10) 朴素递归 = " << FibRec(10) << '\n';
    std::vector<long long> memo(51, -1);
    std::cout << "Fib(50) 记忆化 = " << FibMemo(50, memo)
              << "（朴素递归要算约 200 亿次，根本跑不完）\n";
    std::cout << "汉诺塔 3 个盘子的移动过程：\n";
    Hanoi(3, 'A', 'B', 'C');
    std::cout << "3 个盘子共需 " << hanoiMoves << " 步（= 2³ − 1）\n";
    return 0;
}

3.8.3　用显式栈把递归改写成非递归

既然递归靠的是系统栈，那我们自己开一个栈、把系统栈里的信息搬进去，就能得到非递归版本。 改写的通用套路是问自己两个问题： ① 这一层「还没做完的事情」是什么？② 做完之后要回到哪里？ 把这两样东西打包成一个结构体压进自己的栈，就是「显式栈模拟递归」。

但不是所有递归都值得改写。阶乘的递归是一种「线性递归」，它的显式栈版本本质上就是倒着乘一遍， 直接写成 for 循环更简单 —— 这说明能用迭代直接表达的就别用栈。 真正需要显式栈的，是那些「每层有多个未完成分支、必须记住走到哪儿了」的递归， 比如树的前序遍历、图的 DFS、迷宫回溯 —— 这些也是下一节和第 08 讲的主角。

// binary_tree_preorder_iter.cpp —— 用显式栈实现二叉树的非递归遍历
#include <iostream>
#include <stack>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

/* ---------- 递归版：代码最短，但深度大时有栈溢出风险 ---------- */
void PreOrderRec(TreeNode* root) {
    if (!root) return;
    std::cout << root->val << ' ';      // 访问根
    PreOrderRec(root->left);            // 递归左子树
    PreOrderRec(root->right);           // 递归右子树
}

/* ---------- 非递归前序：自己开栈，先压右孩子再压左孩子 ---------- */
void PreOrderIter(TreeNode* root) {
    if (!root) return;
    std::stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* p = st.top();
        st.pop();
        std::cout << p->val << ' ';      // 出栈即访问（前序：根最先）
        if (p->right) st.push(p->right);  // ★ 先压右孩子
        if (p->left)  st.push(p->left);   // ★ 后压左孩子 → 左孩子先出栈
    }
}

/* ---------- 非递归中序：一路向左压栈，弹出时访问，再转向右子树 ---------- */
void InOrderIter(TreeNode* root) {
    std::stack<TreeNode*> st;
    TreeNode* p = root;
    while (p || !st.empty()) {
        while (p) { st.push(p); p = p->left; }   // 把左链全部压栈
        p = st.top(); st.pop();
        std::cout << p->val << ' ';              // 左子树走完才访问根
        p = p->right;                            // 转向右子树
    }
}

void FreeTree(TreeNode* root) {
    if (!root) return;
    FreeTree(root->left);
    FreeTree(root->right);
    delete root;
}

int main() {
    /*            1
                 / \
                2   3
               / \   \
              4   5   6        */
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    std::cout << "前序（递归）  ："; PreOrderRec(root);  std::cout << '\n';
    std::cout << "前序（显式栈）："; PreOrderIter(root); std::cout << '\n';
    std::cout << "中序（显式栈）："; InOrderIter(root);  std::cout << '\n';
    FreeTree(root);
    return 0;
}

3.8.4　递归 vs 显式栈：该选哪个

3.9　经典应用四：迷宫求解（回溯）

迷宫问题是「栈式回溯」最直观的舞台：从入口出发向前走，把走过的位置记下来； 走到死胡同时，退回上一个岔路口换一个方向再试。整个过程与 3.8.3 的显式栈一脉相承 —— 栈里存的就是「当前这条路径」，出栈就是「回退一步」。

算法描述（方向顺序固定为「上、右、下、左」）：

1. 把入口坐标压栈，并标记为「已走过」。
2. 取栈顶位置，看它的四个方向里还有没有「没试过的、可走的、没走过的」格子： 有就压栈前进，并把该格标记为已走过；
3. 四个方向都试完仍然走不通 → 出栈，回退一步（这就是回溯）。
4. 栈顶到达终点 → 栈里从底到顶就是一条通路；栈空仍未到达 → 迷宫无解。

为什么每个格子「标记为已走过」之后就不用再清除？因为我们的目标是找一条路， 一个格子一旦证明「从这里走不到终点」，再走一次也是白走。 但如果题目要求「找出所有路径」或者「最短路径」，标记就必须在回退时撤销（恢复现场）—— 这正是回溯法与 DFS 的分水岭，也是第 13 讲回溯法的起点。

// maze_stack.cpp —— 迷宫求解：栈式回溯（本质是在图上做深度优先搜索 DFS）
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

const int R = 6, C = 8;                    // 迷宫行数、列数
int maze[R][C] = {                         // 1 = 墙，0 = 通路
    {1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1},
    {1,0,1,0,0,1,0,1},
    {1,0,0,0,1,0,0,1},
    {1,1,0,0,0,1,0,1},
    {1,1,1,1,1,1,1,1}
};
const int sx = 1, sy = 1;                  // 入口（行, 列）
const int ex = 4, ey = 6;                  // 出口（行, 列）
int dr[4] = {-1, 0, 1, 0};                 // 上、右、下、左
int dc[4] = { 0, 1, 0, -1};

struct Pos {
    int r, c;      // 坐标
    int d;         // 下一次要尝试的方向编号（0..3）
};

bool InMaze(int r, int c) { return r >= 0 && r < R && c >= 0 && c < C; }

// 找到一条通路：path 从入口到出口；无解返回 false
bool SolveMaze(std::vector<Pos>& path) {
    int mark[R][C] = {0};                  // 是否已经进过栈（避免原地兜圈子）
    std::stack<Pos> st;                    // ★ 核心：用栈保存当前路径
    st.push({sx, sy, 0});
    mark[sx][sy] = 1;

    while (!st.empty()) {
        Pos cur = st.top();                // 只看，不弹
        if (cur.r == ex && cur.c == ey) {   // 到达出口
            path.clear();
            while (!st.empty()) { path.push_back(st.top()); st.pop(); }
            std::reverse(path.begin(), path.end());   // 栈底 → 栈顶 = 入口 → 出口
            return true;
        }
        int found = -1;                    // 找一个没试过的可行方向
        for (int d = cur.d; d < 4; ++d) {
            int nr = cur.r + dr[d], nc = cur.c + dc[d];
            if (InMaze(nr, nc) && maze[nr][nc] == 0 && !mark[nr][nc]) { found = d; break; }
        }
        if (found >= 0) {                   // 能走 → 前进
            st.top().d = found + 1;        // 记住「这个方向已经试过了」
            int nr = cur.r + dr[found], nc = cur.c + dc[found];
            mark[nr][nc] = 1;
            st.push({nr, nc, 0});
        } else {
            st.pop();                      // 四个方向都不通 → 出栈回退（回溯）
        }
    }
    return false;                          // 栈空仍未到达 → 无解
}

void PrintMaze(const std::vector<Pos>& path) {
    char g[R][C + 1];
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c) g[r][c] = maze[r][c] ? '#' : '.';
    for (size_t i = 0; i < path.size(); ++i) g[path[i].r][path[i].c] = '*';
    g[sx][sy] = 'S';
    g[ex][ey] = 'E';
    for (int r = 0; r < R; ++r) { g[r][C] = '\0'; std::cout << g[r] << '\n'; }
}

int main() {
    std::vector<Pos> path;
    if (SolveMaze(path)) {
        std::cout << "找到通路，共 " << path.size() << " 个格子：\n";
        PrintMaze(path);
        std::cout << "路径坐标：";
        for (size_t i = 0; i < path.size(); ++i)
            std::cout << '(' << path[i].r << ',' << path[i].c << ')' << (i + 1 < path.size() ? " → " : "");
        std::cout << '\n';
    } else {
        std::cout << "迷宫无解\n";
    }
    return 0;
}

3.10　经典应用五：单调栈

前面几个应用都是「栈保存了历史」，这一节的单调栈则多了一层巧思：不仅保存历史，还主动扔掉没用的历史。 它的出场标志是一类非常固定的问题：对每个元素，求它左边 / 右边第一个比它大（或小）的元素。 暴力做法对每个位置都往一边扫一遍，是 O(n²)；单调栈把它压到 O(n)。

3.10.1　下一个更大元素

给定数组 A = [2, 1, 5, 6, 2, 3, 1]，对每个下标 i 求： 在 i 的右边，第一个比 A[i] 大的元素是多少？不存在则记 −1。 答案是 [5, 5, 6, −1, 3, −1, −1]。

关键洞察是：把「还没找到答案的下标」放进一个栈，并保持栈内元素的值单调不增。 当新元素 A[i] 到来时，它就是栈里所有比它小的那些位置的「下一个更大元素」—— 这些位置从此再也不会被用到，可以放心弹出。用一个比喻： 栈里排着一队「等着被人超越」的选手，新来的 A[i] 一出现，就把比自己矮的全部「结算」掉，然后自己站到队尾继续等。

为什么这些被弹出的元素「再也不会被用到」？因为 A[i] 既比它们大、位置又在它们右边， 对它们右边任何还没结算的位置来说，A[i] 都是比它们更优的候选 —— 这就是可以「扔掉历史」的严格理由。

下面的动画把「数组指针、单调栈、答案数组」三者放在一起同步演示，并且会把每一次弹出都单独作为一帧， 方便你看清「谁被谁结算了」。注意栈里存的是下标而不是值 —— 因为我们需要把答案写回 ans[下标]。

// monotonic_stack.cpp —— 单调栈：下一个更大元素 + 直方图中最大矩形
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

/* ① 下一个更大元素：对每个 i，求右边第一个比 A[i] 大的值，不存在记 -1 */
std::vector<int> NextGreater(const std::vector<int>& A) {
    int n = static_cast<int>(A.size());
    std::vector<int> ans(n, -1);
    std::stack<int> st;                            // 存下标；栈内 A[st.top()] 单调不增
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && A[st.top()] < A[i]) {  // A[i] 能「结算」栈顶
            ans[st.top()] = A[i];
            st.pop();
        }
        st.push(i);                                // 每个下标只进栈一次
    }
    return ans;                                    // 仍留在栈里的下标答案保持 -1
}

/* ② 直方图中最大矩形：对每根柱子，找左右第一个比它矮的柱子，宽度 = 右 − 左 − 1 */
long long LargestRectangle(const std::vector<int>& h) {
    int n = static_cast<int>(h.size());
    std::vector<int> left(n, -1), right(n, n);
    std::stack<int> st;
    for (int i = 0; i < n; ++i) {                  // 从左到右 → 左边界
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();
        st.push(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n - 1; i >= 0; --i) {             // 从右到左 → 右边界
        while (!st.empty() && h[st.top()] >= h[i]) st.pop();
        right[i] = st.empty() ? n : st.top();
        st.push(i);
    }
    long long best = 0;
    for (int i = 0; i < n; ++i)
        best = std::max(best, static_cast<long long>(h[i]) * (right[i] - left[i] - 1));
    return best;
}

int main() {
    std::vector<int> A = {2, 1, 5, 6, 2, 3, 1};
    std::vector<int> ans = NextGreater(A);
    std::cout << "A   = ";
    for (int v : A) std::cout << v << ' ';
    std::cout << "\nans = ";
    for (int v : ans) std::cout << v << ' ';
    std::cout << "\n";

    std::vector<int> h = {2, 1, 5, 6, 2, 3};
    std::cout << "直方图 {2,1,5,6,2,3} 的最大矩形面积 = " << LargestRectangle(h) << '\n';
    return 0;
}

3.10.2　直方图中最大矩形：单调栈的第二种用法

题目：给一排宽度都是 1、高度分别为 h[0..n-1] 的柱子（直方图）， 求其中能画出的最大矩形面积。经典数据 h = {2,1,5,6,2,3}，答案是 10 （取高度 5 与 6 两根柱子，宽度 2，面积 5×2 = 10）。

换个角度想：每一个最大矩形，一定是以某根柱子的高度为高的（否则可以再长高）。 所以问题变成：对每根柱子 i，求「以 h[i] 为高时，能向左右扩展多远」—— 也就是找左边第一个比它矮的柱子和右边第一个比它矮的柱子。 这正好又是「第一个更大 / 更小元素」问题，于是两次单调栈搞定。 下面这份代码用「末尾加一个高度 0 的哨兵」的技巧，把两次扫描压缩成一趟。

// largest_rectangle_onepass.cpp —— 直方图最大矩形：单调栈一趟扫描版（哨兵技巧）
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

int LargestRectangleArea(std::vector<int> h) {
    h.push_back(0);                      // ★ 哨兵：高度 0 比所有柱子都矮，保证最后能把栈清空
    std::stack<int> st;                  // 存下标，栈内高度单调递增
    int best = 0;
    for (int i = 0; i < static_cast<int>(h.size()); ++i) {
        while (!st.empty() && h[st.top()] > h[i]) {
            int height = h[st.top()];    // 以被弹出的柱子为高
            st.pop();
            int left = st.empty() ? -1 : st.top();     // 左边第一个更矮的
            int width = i - left - 1;                   // 向右能扩展到 i − 1
            best = std::max(best, height * width);
        }
        st.push(i);
    }
    return best;
}

int main() {
    std::vector<std::vector<int>> tests = {
        {2, 1, 5, 6, 2, 3},              // 10
        {2, 4},                          // 4
        {6, 2, 5, 4, 5, 1, 6},           // 12
        {1},                             // 1
        {2, 2, 2}                        // 6
    };
    for (size_t i = 0; i < tests.size(); ++i) {
        std::cout << "测试 " << (i + 1) << " → " << LargestRectangleArea(tests[i]) << '\n';
    }
    return 0;
}

验算第三组 {6,2,5,4,5,1,6}：高度 4 的柱子（下标 3）左边第一个更矮的是下标 1（高 2）， 右边第一个更矮的是下标 5（高 1），宽度 5-1-1 = 3，面积 4×3 = 12； 高度 5 的两根柱子（下标 2 与 4）被高度 4 隔开，各自宽度只有 1，面积 5 —— 所以最大值是 12 ✓。

3.10.3　复杂度与「什么时候该想到单调栈」

单调栈的时间复杂度证明是均摊分析的又一经典：每个下标恰好进栈一次， 而每次 while 循环都会弹出一个下标，所以整个算法执行期间弹出总次数不超过进栈总次数 n。 把内层循环的次数「摊」到外层，总操作数 ≤ 2n，即 O(n)。 这也解释了为什么双层 for / while 嵌套却是线性时间 —— 看到嵌套循环不要立刻判 O(n²)，要看内层到底执行了多少次。

3.11　栈的其它应用一览

栈之所以被称为「最重要的数据结构之一」，是因为它出现在计算机系统的每一个层次里。 下面五个场景，每一个都只需要一两句话就能解释清楚，但每一个都能体现「后进先出」的威力。

撤销 / 重做是「双栈」最典型的用法，代码短到可以放进一次课堂练习，但它把「栈顶 = 最近的操作」这个直觉用到了极致。

/* ==========================================================================
   撤销 / 重做 —— 两个栈的经典配合
   --------------------------------------------------------------------------
   直觉：栈顶就是「最近发生的事」。
       撤销栈 undo：每次操作压一份记录进去
       重做栈 redo：撤销时把记录从 undo 挪到 redo；重做时再挪回来

   关键的一条规则：**一旦产生了新操作，重做栈就作废**（清空）。
   因为历史已经分叉了，旧的那条"未来"不再是未来。

   竞赛里表达"两个栈"直接用两个全局数组就行，不必封装成类。
   string 用 STL 完全没问题（它属于竞赛常规工具）。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
string undoStk[N];  int undoTop = 0;      // 撤销栈
string redoStk[N];  int redoTop = 0;      // 重做栈
string text = "";                          // 当前文本

void InitEditor() { undoTop = redoTop = 0; text = ""; }

/* ---------- 输入一段文字 = 一次可撤销的操作 ---------- */
void Type(const string &s) {
    text += s;
    undoStk[++undoTop] = s;               // 记入撤销栈
    redoTop = 0;                          // ★ 产生新分支 → 重做栈作废（最容易漏的一句）
}

/* ---------- 撤销：Ctrl+Z ---------- */
bool Undo() {
    if (undoTop == 0) return false;        // 没有可撤销的操作
    string s = undoStk[undoTop--];         // 取出最近那次操作
    text.erase(text.size() - s.size());    // 反向执行：把这段文字删掉
    redoStk[++redoTop] = s;                // 挪到重做栈
    return true;
}

/* ---------- 重做：Ctrl+Y ---------- */
bool Redo() {
    if (redoTop == 0) return false;
    string s = redoStk[redoTop--];
    text += s;                             // 重新执行
    undoStk[++undoTop] = s;
    return true;
}

void Show(const char *title) {
    printf("%-22s text=\"%s\"   撤销栈深度=%d  重做栈深度=%d\n",
           title, text.c_str(), undoTop, redoTop);
}

int main() {
    InitEditor();

    Type("Hello");
    Type(", world");
    Type("!!!");
    Show("输入三次后");

    Undo();
    Show("撤销一次");
    Undo();
    Show("撤销两次");

    Redo();
    Show("重做一次");

    Type("?");
    Show("此时输入新内容");
    printf("→ 重做栈被清空（=0），因为历史已经分叉\n");

    printf("还能重做吗：%s\n", Redo() ? "能" : "不能（重做栈空了）");

    /* ---------- 结论 ----------
       ① 撤销/重做 = 两个栈来回搬元素，每次 O(1)
       ② 产生新操作必须清空重做栈，否则会"重做"出与当前文本矛盾的旧内容
       ③ 变体：浏览器前进/后退按钮、编辑器的多级撤销，都是这个模型
       ④ 更进一步：把"操作"设计成可逆的对象（do/undo 成对），
          就能支持任意复杂操作的撤销——这就是命令模式的核心思想 */
    return 0;
}

3.12　工程视角：栈在真实系统里出现在哪

前面十一节，我们一直把栈当「课本里的数据结构」用：用数组实现它、用链表实现它， 再拿它去解括号匹配、表达式求值和单调栈。这一节换个视角 —— 看真实的机器里，栈出现在哪些地方。每个落点都回答同样三个问题： 用的是什么结构 → 为什么非它不可 → 代价是什么。

3.12.1　函数调用栈：一个栈帧里装了什么

3.8 节说过「递归能自动回溯，是因为函数调用栈」，现在把这句话拆到机器级别。 当 f 调用 g，CPU 执行一条 call 指令，动作可以简化成两件事 —— 把「返回地址」压入栈，跳到 g 的第一条指令； g 执行完的 ret 反过来做两件事 —— 从栈顶弹出返回地址，跳回去。 一压一弹，就是栈最原始的两个操作。

g 干活期间还需要一块自己的空间：参数和局部变量放在哪？ 函数返回后，要把调用者用过的寄存器恢复成什么样？ 这些信息被打包成一块连续内存压到栈顶，就是栈帧（stack frame），通常含四类内容： 返回地址、保存的寄存器（主要是上一帧的栈底指针 rbp）、 参数与局部变量，以及编译器为内存对齐和调试信息留出的空隙。

为什么必须是栈，而不是别的结构？因为函数调用本身就是嵌套的： g 不返回，f 就绝不能继续算；f 不返回，main 也绝不能继续。 最后被调用的函数一定最先返回 —— 这正是后进先出。 换成队列就变成「先调用的先返回」，main 会在 g 还在跑时抢着往下执行，程序立刻失去意义。 所以说不是「栈刚好适合函数调用」，而是函数调用这种嵌套关系本身就定义了一个栈，硬件把它直接实现出来了。

代价是什么？好处是压栈、弹栈只需把栈顶指针 rsp 加减一个数，快到几乎免费， 而且这块内存连续、缓存命中率极高，任何堆分配都比不了。 代价集中在一条：栈的大小是固定的 —— 线程创建时就定死（Windows 默认 1MB，Linux 默认 8MB）， 没有「动态扩容」这回事，用超了只有崩溃。

3.12.2　栈溢出：为什么大数组不能开在局部变量里

局部变量住在栈帧里，所以局部数组的每一格都要从这块有限的栈空间里扣。 这是初学者最常撞上的一堵墙：在函数里写下 char buf[8 * 1024 * 1024];， 函数一被调用程序就崩，报错信息还常常指向一行看起来毫无问题的代码。

原因很直接：8MB 的局部数组要求编译器在一帧里腾出 8MB，而 Windows 默认栈只有 1MB。 函数刚一进入，「调整栈指针」那一条指令执行完就访问到了栈范围之外的地址： Windows 上的现象是错误码 0xC0000005（访问冲突），Linux 上是 SIGSEGV（段错误）。 整个过程中编译器和链接器都不会拦你，错误要等程序真的跑进那个函数才发作 —— 这正是它难查的原因。

对策就是让大数组改住数据段：写成全局变量或 static 局部变量。 static 的语义是「生命周期贯穿整个程序」，它不可能住在「函数返回就销毁」的栈帧里， 编译器会把它安排进数据段（未初始化的部分叫 BSS），程序启动时就分配好。 数组还是那个数组，唯一改变的是它住在哪一段内存 —— 第 02 讲讲顺序表与链表时说的「同一份数据、不同存放方式，代价完全不同」，在这里又出现了一次。

第二种成因是递归太深：一个栈帧若占 64 字节，1MB 的栈只装得下约 1.6 万层调用。 快排在逆序数据上退化、图的深搜（第 09 讲）沿长链一路递归，都会撞上这堵墙。 对策一是 3.8.3 的「自己开一个数组当栈，把递归改写成非递归」， 二是改写成按层递推（第 13 讲会系统讲这类改写）。 递归版更短更好读，显式栈更稳更可控 —— 一次典型的工程取舍。

/* ==========================================================================
   stack_frame_demo.cpp —— 调用栈与栈帧：栈溢出到底是怎么发生的
   编译：g++ -std=c++17 -O2 stack_frame_demo.cpp -o stack_frame_demo
   运行：缩进越来越深，再一层层退回来 —— 那正是调用栈在压栈和弹栈。
   ========================================================================== */
#include <cstdio>

/* ---------- ① 递归：每一层调用 = 往栈上压入一个栈帧 ---------- */
void Trace(int depth, int maxDepth) {
    int localSlot = depth * 10;          // 住在「本层栈帧」里的局部变量
    for (int i = 0; i < depth; ++i) printf("    ");
    printf("压栈 f(%d)   本层局部变量 localSlot = %d\n", depth, localSlot);

    if (depth < maxDepth) Trace(depth + 1, maxDepth);   // 递归 = 继续往栈上压

    for (int i = 0; i < depth; ++i) printf("    ");
    printf("弹栈 f(%d)   本层结束，回到上一层\n", depth);
}

/* ---------- ② 大数组必须放数据段，不能放在栈上 ---------- */
const int N = 1000000;                   // 100 万个 long long = 8MB

long long SumBigArray() {
    static long long big[N];             // ✅ 数据段（BSS）：不占栈帧，程序启动时就分配好
    /* long long big[N];                 // ❌ 若写成这样，一帧就要 8MB，
                                         //    而 Windows 默认栈只有 1MB —— 一被调用就崩：
                                         //    错误码 0xC0000005 / Linux 上是 SIGSEGV
       另一种安全写法：long long big[N];  // 全局变量 → 也进数据段
       判断口诀：把「数组长度 × sizeof(元素)」算成字节数，
       超过几万字节，就别把它当函数体里的局部数组。 */

    for (int i = 0; i < N; ++i) big[i] = i;
    long long sum = 0;
    for (int i = 0; i < N; ++i) sum += big[i];
    return sum;
}

/* ---------- ③ 缓冲区越界为什么会改掉返回地址（原理示意，不给出可运行的攻击代码） ----------
   把图 3-13 的栈帧按地址从高到低画出来：

        高地址 ┌────────────────────────────┐
               │  ★ 返回地址                 │ ← ret 指令从这里取地址跳回去
               ├────────────────────────────┤
               │  保存的 rbp（上一帧的栈底）  │
               ├────────────────────────────┤
               │  int x;  double y;  等局部量 │
               ├────────────────────────────┤
        低地址 │  char buf[8]  下标增大 →     │
               └────────────────────────────┘

   strcpy(buf, src) 不检查长度：只要 src 超过 8 个字节，
   多出来的字节就顺着「低地址 → 高地址」的方向一路写过去：
   先淹没 buf 自己，再淹没局部变量、保存的 rbp，最后「盖掉返回地址」。
   函数返回时 CPU 从栈顶取出这个已经被改写的地址跳转 —— 这就是栈溢出攻击。

   防线见正文 3.12.3 的四层（代码层 / 编译器金丝雀 / NX / ASLR）。
   本节只讲原理，不给出可运行的攻击代码。
   ------------------------------------------------------------------------- */

int main() {
    printf("① 递归的压栈 / 弹栈过程（缩进就是栈的深度）：\n");
    Trace(0, 4);

    printf("\n② 同一个 8MB 的大数组，放 static（数据段）就平安无事：\n");
    printf("   sum = %lld   而栈上只占了一个函数帧的几十个字节\n", SumBigArray());

    printf("\n③ 结论：局部变量的空间来自栈帧，而栈很小（Windows 1MB / Linux 8MB）；\n");
    printf("   大数组一律开成全局或 static，让编译器把它安排到数据段去。\n");
    return 0;
}

3.12.3　栈与缓冲区溢出攻击：返回地址为什么会被改掉

回到图 3-13，注意布局里的一个细节：返回地址和局部缓冲区挨着放， 返回地址在高地址那一侧，而数组下标增大的方向也正朝着高地址。 这两个事实凑在一起，构成了计算机安全史上最著名的一类漏洞。

strcpy(buf, src) 不检查长度，会一直复制到 src 的结尾。 只要 src 比 buf 长，多出来的字节就顺着高地址方向一路写过去： 先淹没 buf 自己，再淹没旁边的局部变量和保存的寄存器，最后盖掉返回地址。 等函数执行到 ret，CPU 老老实实弹出这个已被改写的地址跳过去 —— 攻击者没调用任何函数，只是多写了几个字节，就劫持了程序的执行流。 这就是栈溢出攻击（stack smashing）。

现代变种叫 ROP（面向返回编程）：就算栈被标记为不可执行，攻击者也不必注入自己的代码， 只要把返回地址改成一连串程序里本来就有的代码片段（gadget，通常是「几条指令跟一个 ret」）的地址， 每次 ret 跳一小段，像拼乐高一样拼出完整攻击。 到这一步，栈已经不只是受害者，它是攻击的执行引擎。

防线分四层，每层都对应前面讲过的一个概念：

• 代码层：不用 strcpy / strcat / gets / sprintf， 改用 snprintf 或 std::string；关键是长度上限要来自目标缓冲区的大小 （sizeof(buf)），而不是源字符串的长度 —— 后者等于没设限。
• 编译器层：栈保护金丝雀（canary）。在返回地址和缓冲区之间塞一个随机数， 函数返回前检查它有没有被改动，改了就立刻终止程序。 代价：每次调用多两次内存访问和一次比较；而且它是「事后报警」，能阻止劫持，阻止不了越界本身。
• 操作系统层：不可执行栈（NX / DEP）。栈所在的内存页标记为不可执行， 攻击者跳进栈里也执行不了自己写的字节。 代价：浏览器的 JIT 得一边生成机器码一边改内存页属性，复杂度与受攻击面都上升 —— 这也是 ROP 被发明出来的直接原因。
• 系统层：地址随机化（ASLR）。每次启动栈地址都不同，攻击者猜不到返回地址该填什么。 代价：调试更麻烦，而且它只让攻击者「猜不中」，不是「做不到」。

一句话总结：栈让函数调用变得极快，代价是「返回地址躺在一段可写内存里」。 从 1988 年的 Morris 蠕虫到今天，整个栈安全领域都在给这一个代价打补丁 —— 这是栈在真实世界里存在感最强的地方。

3.12.4　编译器与虚拟机：两个栈一起干活

3.7 节手写的「运算符栈 + 操作数栈」，在真实编译器里是同一个模型的放大版： 语法分析器一边读记号，一边用运算符栈（更一般的说法是「状态栈」）决定 「现在结算，还是先压起来等右边」；左括号的作用就是把栈里的东西全部挡住 —— 你写的 isp / icp 比较规则，就是算符优先分析表的简化版。 表达式最终被组织成一棵表达式树（图 3-8）：前序遍历得前缀式，后序遍历得后缀式， 这棵树在第 07 讲会以「二叉树」的身份重新出现。

虚拟机把栈用得更彻底。栈式虚拟机几乎不用通用寄存器，所有计算都围绕一个操作数栈： iload 把局部变量压到栈顶，iadd 弹出两个整数、相加、把结果压回去， istore 再把栈顶存回局部变量表。一段 a + b * c 编译出来大致是：

对照 3.7.4 那张「后缀求值的操作数栈变化表」，你会发现两者一模一样 —— 后缀表达式就是栈式虚拟机的汇编语言。连方法调用也是同一套： 每次调用都在 Java 栈上压入一个新栈帧，里面装这个方法的局部变量表和它自己的操作数栈， 和图 3-13 是同一个思路。

为什么虚拟机用栈式，而不像真实 CPU 那样用寄存器？ 因为栈式指令短、规整、不依赖硬件有多少个寄存器：操作数隐含在栈顶，平均一两个字节一条， 字节码文件小、解释器简单、JIT 验证也容易。代价是完成同样的计算要执行更多指令、更多次访存， 纯解释执行不如寄存器式。所以 Lua 5.4、Android 的 Dalvik/ART 都转向了寄存器式字节码 —— 又一个「实现简单 ↔ 执行高效」的取舍，和 3.4.2 里顺序栈与链栈的取舍是同一种思维。

3.12.5　嵌套结构：括号匹配的工业化版本

3.5 节的括号匹配在工程里无处不在：文件路径 /usr/local/bin 的层级、 XML / HTML 的标签配对、JSON 的 { } 与 [ ]、语言里的代码块 —— 嵌套结构的标准处理工具都是栈。

最具体的例子是浏览器解析 HTML：解析器内部维护一个「打开元素栈」， 读到 <div> 压栈，读到 </div> 与栈顶比对，对上就弹出 —— 和 3.5.3 的 Match 是同一个逻辑，只是元素从括号字符换成了标签对象。 更有意思的是错误恢复：真实网页经常漏写闭合标签，浏览器不能让页面因此打不开， 于是「栈顶对不上就把栈顶弹掉，继续解析」。标签写错的网页还能凑合显示， 靠的正是在栈上做的一次有策略的退栈。

JSON 解析器同理，而这里藏着一个和 3.12.2 呼应的安全问题：嵌套深度可以被恶意构造。 几十 KB 却嵌套几十万层的 JSON，用递归下降实现的解析器会直接爆栈； 所以工业解析器要么改成显式栈（正是「自己用数组模拟一个栈」），要么给深度设硬上限。 栈给了你处理嵌套的能力，也给了你一个必须设防的入口。

3.12.6　单调栈的工程落点

3.10 的单调栈不是竞赛花招，它在工程上对应一整类流式统计问题， 典型代表是股票跨度（stock span）：给定每天股价，求每一天「在此之前连续多少天价格不高于今天」， 也就是找左边第一个比今天高的价格，两者下标之差就是跨度。 这正是 3.10.1「下一个更大元素」的镜像 —— 把扫描方向反过来、把右边换成左边即可。

同类还有：每日温度（下一个更大元素）、柱状图中最大矩形 （3.10.2 写过，也是图像与数据分析里「直方图最大内接矩形」的标准解法）， 以及各种「右边第一个比我矮的楼」式的监控指标。

它为什么值钱？因为它把「每个位置回头翻一遍历史」的代价从 O(n) 降到摊还 O(1)： 暴力做法每个位置向左扫一遍，总共 O(n²)；单调栈只做一件事 —— 把「还没找到答案」的下标按单调性留在栈里，新元素一到就顺手结算掉已有答案的那些。 每个下标进栈一次、出栈一次，总操作 ≤ 2n（第 01 讲的大 O 在这里体现得非常干净）。 对每天上百万条的行情流，O(n²) 和 O(n) 是「跑不动」与「毫秒级」的区别。

边界也很清楚：下标一旦被弹出，信息就永久丢失 —— 这既是 O(n) 的原因，也是它的天花板， 它只能回答「第一个更大 / 更小」，问「任意区间最大值」得换稀疏表或线段树。 别和单调队列搞混：单调栈元素只从一端进出，处理「找第一个更大 / 更小」； 单调队列两端都会进出，处理「滑动窗口最值」，第 04 讲会专门讲。 「栈里存值还是存下标」这个坑，工程代码里同样踩一次记一辈子。

3.12.7　三种栈的工程对比

最后把这一节出现的三种「栈」放在一张表里对比。它们的抽象接口完全一样 （push / pop / top），但因为底层载体不同， 工程属性差了十万八千里 —— 「数据结构 = 逻辑结构 + 存储结构」这句话不是空话。

3.13　本章小结、易错点与自测

3.13.1　一页纸小结

把这一章压缩成一张表：三种实现 + 五个应用 + 两句话的本质。

3.13.2　易错点清单

3.13.3　考点清单

3.13.4　自测题（4 题）

// 求「下一个更小元素」：与「下一个更大」只差一个比较符号
// 求更小 → 用递增栈（栈底小、栈顶大）：栈顶比当前元素大就弹
#include <iostream>
#include <vector>
#include <stack>

std::vector<int> NextSmaller(const std::vector<int>& A) {
    int n = static_cast<int>(A.size());
    std::vector<int> ans(n, -1);                 // 默认 -1：右边没有更小的
    std::stack<int> st;                          // 存下标，栈内值单调递增
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && A[st.top()] > A[i]) {   // 只有「>」与求更大时不同
            ans[st.top()] = A[i];
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

int main() {
    std::vector<int> A = {3, 1, 4, 1, 5, 9, 2, 6};
    std::vector<int> ans = NextSmaller(A);
    for (int v : ans) std::cout << v << ' ';
    std::cout << '\n';                            // 1 -1 1 -1 2 2 -1 -1
    return 0;
}