线性结构 · 第 03 讲

第 03 讲 栈及其经典应用

栈是「后进先出」的受限线性表,也是整个数据结构课程里性价比最高的一章: 它的结构简单到只有一句话,却能解决括号匹配、进制转换、表达式求值、递归消除、迷宫回溯、单调栈优化这一长串经典问题。 本讲把栈的三种存储实现讲透,再用可单步、可播放的动画把每个应用的执行过程拆开给你看。

预计 120 分钟 前置:第 02 讲 线性表(顺序表与链表) 关键词:LIFO · 顺序栈 · 共享栈 · 链栈 · 中缀转后缀 · 单调栈
本章导读
  • 概念层:栈的定义、LIFO 特性、为什么必须「只在栈顶操作」,栈顶 / 栈底 / 空栈 / 上溢 / 下溢五个术语,以及栈的 ADT 七个操作。
  • 存储层:顺序栈(数组 + top,含 top 的两种约定)、共享栈(两个栈抢一个数组)、链栈(用单链表实现),三者放在一张表里对比。
  • 应用层:括号匹配 → 进制转换 → 表达式求值(中缀转后缀 / 后缀求值) → 栈与递归 → 迷宫回溯 → 单调栈(下一个更大元素)。
  • 动画层:6 个交互动画,全部支持「▶ 播放 / ◀ 上一步 / 下一步 ▶ / ⏮ 重来 / ⏭ 末帧」与速度调节,建议逐帧对着说明栏看。
  • 代码层:18 段可直接编译运行的 C++ 代码,统一用竞赛写法(全局数组 + 普通函数,出错用返回值报告),都带 main 测试。

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

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

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

栈 stack:只允许在同一端插入与删除 12 7 25 3 Push 入栈 Pop 出栈 ← 栈顶 top(唯一可操作端) ← 栈底 bottom(封死) LIFO:后进先出 入栈序:12 → 7 → 25 → 3 出栈序:3 → 25 → 7 → 12 · 只能在栈顶插入 / 删除 · 栈底元素最先入栈、最后出栈 · 不允许按下标随机访问 · 所有基本操作都是 O(1) · 空栈 Pop = 下溢;满栈 Push = 上溢
图 3-1 栈的 LIFO 特性:入栈与出栈都发生在栈顶,出栈序列恰好是入栈序列的逆序

3.1.1 五个必须背下来的术语

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

栈 stack
限定仅在表尾进行插入和删除操作的线性表。表尾叫栈顶,表头叫栈底。逻辑结构仍是线性表,物理结构可以顺序也可以链式。
栈顶 top
允许插入和删除的那一端,是栈里唯一「活着」的位置。所有操作(Push / Pop / GetTop)都围绕它展开,因此代码里几乎每一行都有 top。
栈底 bottom
不允许操作的那一端。栈底元素是第一个入栈的元素,也只有当栈里其他元素全部弹出后,它才能出栈。
空栈 empty
不含任何元素的栈。顺序栈里通常写作 top == -1(top 指向栈顶元素下标)或 top == 0(top 指向栈顶上方空位)。判空是 Pop 与 GetTop 的第一道防线。
上溢 / 下溢
上溢 overflow:栈满时继续 Push,数组已经没有空位;下溢 underflow:栈空时继续 Pop 或 GetTop,根本没有元素可取。 上溢是空间不够,下溢是逻辑错误 —— 前者可以靠扩容或换链栈避免,后者只能靠程序员自己检查。
易错:上溢不是「数组越界」那么简单 顺序栈的 Push 必须先判满。C++ 里对 std::vector 用 v[++top] 越界写是未定义行为, 在 Release 下可能「看起来能跑」,考试时却会直接判错。正确顺序永远是:先判满 → 再移动 top → 最后写入; 出栈则是:先判空 → 再取值 → 最后移动 top。

3.1.2 栈的 ADT 与操作集

ADT(Abstract Data Type,抽象数据类型)回答的是「这个结构能做什么」,而不回答「它怎么做到的」。 学数据结构最忌讳一上来就背数组下标 —— 先把 ADT 想清楚,你会发现顺序栈、链栈、共享栈的接口完全一样, 只是实现不同,甚至可以互相替换而调用方毫不知情。这正是抽象的价值。 本讲的顺序栈、链栈都按下表写成同名函数(共享栈多一个参数 i,指明操作的是 0 号还是 1 号栈); 出错时返回 false。

操作语义前置条件时间复杂度
InitStack()构造一个空栈(初始化)—O(1)
StackEmpty()判空:空返回 true—O(1)
StackFull()判满:满返回 true只有顺序栈有;链栈不会满,不提供O(1)
Push(x)入栈:把 x 放到栈顶,成为新的栈顶栈不满,否则上溢,返回 falseO(1)
Pop(e)出栈:删除栈顶元素并用 e 带回栈不空,否则下溢,返回 falseO(1)
GetTop(e)取栈顶:用 e 带回,只读,不删除栈不空O(1)
ClearStack()清空:回到初始空栈状态—O(1)(顺序栈置 top);O(n)(链栈逐个 delete)
StackLength()求长度:返回元素个数—O(1)(链栈用一个计数器 cnt 记着)
学习顺序建议 这一节只要记住一句话:栈 = 只能在栈顶进出的线性表。剩下的全是实现细节。 接下来 3.2 / 3.3 / 3.4 分别讲三种实现,3.5 之后全是应用 —— 每个应用都会回到这句话来解释「为什么必须用栈」。

3.2 顺序栈:用数组实现

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

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

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

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

约定 A:top 指向「栈顶元素的下标」

  • 空栈:top == -1
  • 栈满:top == MaxSize - 1
  • 入栈:S[++top] = e
  • 出栈:e = S[top--]
  • 取栈顶:S[top]
  • 长度:top + 1

约定 B:top 指向「栈顶上方空位」

  • 空栈:top == 0
  • 栈满:top == MaxSize
  • 入栈:S[top++] = e
  • 出栈:e = S[--top]
  • 取栈顶:S[top - 1]
  • 长度:top(本身就是长度)
约定 A:top 指向栈顶元素(本章代码采用) 12 7 25 012 345 top = 2 空栈:top = −1 栈满:top = MaxSize − 1 入栈:S[++top] = e 出栈:e = S[top−−] 长度:top + 1 = 3 空栈是 −1,所以「判空」要写成 top == −1 约定 B:top 指向栈顶上方空位 12 7 25 012 345 top = 3(下一格空位) 空栈:top = 0 栈满:top = MaxSize 入栈:S[top++] = e 出栈:e = S[−−top] 长度:top = 3(天然等于长度) 空栈是 0,判空写成 top == 0,与数组下标无关
图 3-2 同一个数组、同样的三个元素,两种 top 约定下 top 的位置与公式完全不同

3.2.2 顺序栈完整代码(约定 A)

下面这份代码采用约定 A(top 指向栈顶元素,空栈时 top == -1),也是做题时最常用的写法: 一个全局数组、一个 top,再加几个普通函数。栈满、栈空都用返回值 false 报告, 调用方一看返回值就知道这次操作有没有成功。main 把入栈、出栈、取栈顶、清空都跑了一遍。

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

   约定 A:top 指向**栈顶元素**,top == -1 表示空栈,元素存在 a[0..top]。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int a[N];
int top = -1;

void InitStack()    { top = -1; }
void ClearStack()   { top = -1; }          // 清空:top 回到空栈状态,旧值留在数组里没关系
bool StackEmpty()   { return top == -1; }
bool StackFull()    { return top == N - 1; }
int  StackLength()  { return top + 1; }

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 = 0; i <= top; ++i) printf("%d ", a[i]);
    printf("| top=%d\n", top);
}

int main() {
    InitStack();
    PrintStack("空栈");                          // | top=-1

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

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

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

    ClearStack();
    PrintStack("ClearStack 后");                  // | top=-1

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

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

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

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

看动画时请盯住三个数字 ① top 的值;② 数组里「属于这个栈」的格子数(也就是长度 top + 1); ③ 底部状态行的 StackEmpty / StackFull。 出栈后数组里那个旧值并没有被清除,只是不再属于这个栈 —— 这一点在动画里看得很清楚, 也是「顺序栈清空只需 top = -1」的原因。
本节从略 动态扩容与摊还分析从略:顺序栈按题目数据范围把数组开够,满了报错即可。

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

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

做法是:仍然只申请一个数组 data[0..MaxSize-1], 但让0 号栈的栈底固定在左端、1 号栈的栈底固定在右端,两个栈顶各自向中间生长。 0 号栈入栈时 top0 右移,1 号栈入栈时 top1 左移; 只有当两个栈顶迎面撞上、中间一个空位都不剩时,才算「整个数组满了」。 也就是说,只有当两个栈的元素个数加起来占满整个数组时才会上溢:一个栈用得少,另一个栈就能多用, 不再被死死限制在「各自一半」。

一个数组 data[0 .. 7],两个栈底分别钉在两端,两个栈顶向中间长 0 号栈(左端 → 右) 1 号栈(右端 → 左) 12 7 25 5 42 88 012 345 67 top0 = 2 top1 = 5 空闲 2 格 栈满判定 top0 + 1 == top1 (两个栈顶之间再无空位) 0 号栈空:top0 == −1 1 号栈空:top1 == MaxSize
图 3-3 共享栈:两个栈底固定在数组两端,栈顶向中间生长,只有「撞上」才算满
/* ==========================================================================
   共享栈 —— 两个栈共用一个数组,从两端往中间长
   --------------------------------------------------------------------------
   场景:需要两个栈,但它们的容量此消彼长(一个用得多、另一个就用得少)。
   如果各开一个定长数组,就得给两边都按最坏情况开,浪费一半空间。

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

   这样总容量 N 完全共享,只有「两个栈的总元素数」超过 N 才会上溢。
   (注意:不是各自能用到 N,而是加起来 N。)

   操作和 3.1.2 的 ADT 表一一对应,只是多一个参数 i(0 或 1)说明操作哪个栈。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

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

void InitStack() { top0 = -1; top1 = N; }              // 两个栈都置空

void ClearStack(int i) {                               // 清空第 i 号栈
    if (i == 0) top0 = -1; else top1 = N;
}
bool StackEmpty(int i) { return i == 0 ? top0 == -1 : top1 == N; }
bool StackFull()       { return top0 + 1 == top1; }    // 两个栈顶相邻 = 整个数组满了(两个栈共用)
int  StackLength(int i) { return i == 0 ? top0 + 1 : N - top1; }

bool Push(int i, int x) {  // 第 i 号栈入栈:0 号向右长,1 号向左长
    if (StackFull()) return false;
    if (i == 0) a[++top0] = x;
    else        a[--top1] = x;
    return true;
}
bool Pop(int i, int &e) {
    if (StackEmpty(i)) return false;
    if (i == 0) e = a[top0--];
    else        e = a[top1++];
    return true;
}
bool GetTop(int i, int &e) {
    if (StackEmpty(i)) return false;
    e = (i == 0) ? a[top0] : a[top1];
    return true;
}

void PrintStack() {        // 打印整个数组,直观看到两个栈怎么"夹"住中间
    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, StackLength(0), top1, StackLength(1));
}

int main() {
    InitStack();
    printf("初始:0 号空=%d 1 号空=%d 满=%d\n", StackEmpty(0), StackEmpty(1), StackFull());

    for (int x : {1, 2, 3}) Push(0, x);        // 0 号栈:1 2 3
    for (int x : {9, 8})    Push(1, x);        // 1 号栈:9 先入(在最右边),8 后入
    PrintStack();

    int e = 0;
    Pop(0, e); printf("0 号栈弹出 %d\n", e);     // 3
    Pop(1, e); printf("1 号栈弹出 %d\n", e);     // 8(最后压入的先出)
    GetTop(1, e); printf("1 号栈现在的栈顶 = %d\n", e);   // 9
    PrintStack();

    ClearStack(0);
    printf("清空 0 号栈后:0 号长度 = %d,1 号长度 = %d\n", StackLength(0), StackLength(1));   // 0,1

    /* 用一个小容量演示"栈满" */
    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 才报上溢。这就是共享栈最实在的价值 —— 用同一块空间同时服务两个「此消彼长」的栈,把「一个撑死、一个饿死」的概率降到最低。

场景两个独立顺序栈(各 n/2)共享栈(共 n)
两个栈都恰好用 n/2都能装下都能装下
0 号栈用 n,1 号栈空0 号栈上溢能装下
0 号栈用 0.7n,1 号栈用 0.3n0 号栈上溢(浪费 0.2n)能装下
两栈元素总数超过 n上溢上溢(不可避免)
空间利用率最坏 50%接近 100%
考点:共享栈的判满与长度 ① 判满 top0 + 1 == top1;② 0 号栈长度 top0 + 1,1 号栈长度 MaxSize - top1; ③ 空闲个数 top1 - top0 - 1;④ 共享栈的意义是提高空间利用率、减少上溢概率, 但它不会降低时间复杂度,所有操作仍是 O(1)。考选择题时,「共享栈的入栈操作比普通顺序栈慢」是错的。

3.4 链栈:用单链表实现

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

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

链栈:top 指向首元结点,栈底结点的 next == nullptr top 25 • 7 • 12 ∧ 栈顶结点 栈底 bottom Push(x):头插,O(1) Node *p = new Node(x); p->next = top; top = p; 后两句只改两个指针,与栈里已有多少元素无关 Pop(e):删除首元结点,O(1) Node *p = top; e = p->data; top = top->next; delete p; 必须先保存 top,再把 top 后移,最后释放
图 3-4 链栈:单链表的头部就是栈顶,入栈出栈都只改两个指针
看清类型:top 和 p 都是指针,不是结点 top、p 的类型都是 Node*,存的是某个结点的地址 (new Node(x) 返回的就是新结点的地址);p->next 是 p 所指结点里的 next 字段,类型同样是 Node*。 所以入栈那几句全是「地址赋值」:p->next = top 把旧栈顶结点的地址写进新结点的 next,让新结点指向旧栈顶; top = p 把新结点的地址交给 top,让 top 改指新结点。 两句都是指针赋给指针,没有哪一句在复制结点本身。平时说的「栈顶是 top」,准确说法是「top 指向的那个结点是栈顶结点」。

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

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

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

第二,为什么不需要判满。顺序栈的「满」来自「数组下标有上限」这一物理事实。 链栈的结点是运行时用 new 从堆上要来的,只要堆还有内存就能继续 Push, 所以链栈不需要 StackFull() 这个操作,下面的代码也没有写它。 严格地说,整台机器的内存用光时 new 也会失败,但那不是栈本身的容量限制, 做题时不用考虑。

易错:出栈时先删结点还是先移动 top? 错误写法:delete top; top = top->next; —— delete 之后 top 指向的内存已经归还给系统, 再读 top->next 就是访问已释放内存(use after free),程序可能崩溃、可能「碰巧正常」, 是最难查的一类 bug。正确顺序是先保存、再前移、最后释放: Node* p = top; top = top->next; delete p;。
/* ==========================================================================
   链栈 —— 用单链表实现栈,只在「表头」插入和删除
   --------------------------------------------------------------------------
   为什么链栈的所有操作都是 O(1)?
   因为栈的插入删除都发生在**同一端**,我们让那一端正好是链表的表头:
       入栈 = 头插,出栈 = 删首元结点 —— 这两个都是 O(1),不需要找前驱。
   (对比:如果让栈顶在链表尾部,出栈就得先找前驱,退化成 O(n)。)

   链栈的特点(考点):
       ① 不需要判满(只要内存够就能一直 push),所以**没有上溢**
       ② 但要注意判空(空栈出栈就是下溢)
       ③ 头结点可有可无。这一段先用「带头结点」的版本(很多教材这么写),
          不带头结点的版本见下一段 —— 对栈来说那种反而更简单。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

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

Node *head;                 // 头指针,指向头结点(不存数据);栈顶元素是 head->next
int cnt = 0;                // 元素个数,维护它就能 O(1) 求长度

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

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

/* ---------- 出栈 = 删掉首元结点,O(1) ---------- */
bool Pop(int &e) {
    if (StackEmpty()) return false;    // 下溢:空栈不能弹
    Node *p = head->next;              // p 就是栈顶结点
    e = p->data;
    head->next = p->next;              // 摘掉它
    delete p;                          // 先摘链再释放,顺序不能反
    --cnt;
    return true;
}

bool GetTop(int &e) {
    if (StackEmpty()) return false;
    e = head->next->data;              // 带头结点时,栈顶要多跳一次 head->next
    return true;
}

/* ---------- 清空:逐个出栈,每个结点都 delete 掉,O(n) ---------- */
void ClearStack() {
    int e = 0;
    while (Pop(e)) {}
}

void PrintStack(const char *title = "") {     // 从栈顶到栈底打印
    printf("%s(栈顶→栈底):", title);
    for (Node *p = head->next; p; p = p->next) printf("%d ", p->data);
    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 = 0;
    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

    for (int x : {1, 2, 3}) Push(x);
    ClearStack();
    printf("压入 1 2 3 再 ClearStack,长度 = %d\n", StackLength());   // 0
    return 0;
}
/* ==========================================================================
   链栈(不带头结点版)—— top 直接指向栈顶结点,链栈的通行写法
   --------------------------------------------------------------------------
   带头结点时,栈顶元素是 head->next,空栈是 head->next == nullptr;
   不带头结点时,top 直接指向**栈顶结点**,空栈就是 top == nullptr。

   对栈来说,不带头结点反而更简单:所有操作都只在 top 这一端,
   入栈「新结点指向旧 top,再让 top 指向新结点」、出栈「top 后移一格」,
   这两句在空栈 / 只剩一个元素时同样成立,一个特判都不用写。
   ========================================================================== */
#include <bits/stdc++.h>
using namespace std;

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

Node *top = nullptr;         // 直接指向栈顶结点;nullptr 表示空栈
int cnt = 0;

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

/* ---------- 入栈:新结点指向旧栈顶,top 再指向新结点(空栈时也成立) ---------- */
bool Push(int x) {
    top = new Node(x, top);              // 空栈时 top 是 nullptr,新结点的 next 也就是 nullptr ✓
    ++cnt;
    return true;
}

/* ---------- 出栈:先保存 top,再后移 top,最后释放 ---------- */
bool Pop(int &e) {
    if (StackEmpty()) return false;
    Node *p = top;
    e = p->data;
    top = p->next;                       // 只剩一个元素时,top 自然变成 nullptr
    delete p;
    --cnt;
    return true;
}

bool GetTop(int &e) {
    if (StackEmpty()) return false;
    e = top->data;                       // 不带头结点时,top 所指的就是栈顶结点,不用多跳一次
    return true;
}

/* ---------- 清空:逐个出栈,每个结点都 delete 掉,O(n) ---------- */
void ClearStack() {
    int e = 0;
    while (Pop(e)) {}
}

void PrintStack(const char *title = "") {
    printf("%s(栈顶→栈底):", title);
    for (Node *p = top; p; p = p->next) printf("%d ", p->data);
    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 = 0;
    GetTop(e);
    printf("栈顶 = %d(就是 top 所指的结点)\n", e);   // 3

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

    Push(7); Push(8);
    ClearStack();
    printf("压入 7 8 再 ClearStack,top = %s\n", top == nullptr ? "NULL" : "非空");   // NULL

    /* ---------- 两种链栈对比 ----------
       带头结点:多占一个结点;取栈顶要写 head->next,判空写 head->next == nullptr
       不带头结点:top 就是栈顶,判空就是 top == nullptr,入栈出栈都不用特判
       所以链栈一般写成不带头结点的这种。 */
    return 0;
}

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

比较维度顺序栈链栈
存储方式 一段连续数组 + top 下标 一组离散结点,每个结点含数据域与指针域
Push / Pop / GetTop O(1)(动态扩容时为摊还 O(1),单次最坏 O(n)) 严格 O(1),无扩容、无搬移
求长度 StackLength O(1):top + 1 用计数器 cnt 记着就是 O(1)(本讲两段代码都这么做);不设计数器就要从头数,O(n)
清空 ClearStack O(1):top = -1 O(n):必须逐个 delete,否则内存泄漏
是否需预分配容量 需要(或在运行中扩容搬移) 不需要,随用随申请
是否有上溢 有:栈满(top == N - 1)时再 Push 就上溢 无容量上溢(除非内存耗尽)
是否有下溢 有:空栈 Pop / GetTop 有:空栈 Pop / GetTop(top == nullptr)
空间开销 无额外指针;但可能预留过多或不足 每个元素多一个指针域(64 位下 8 字节)+ 分配器管理开销
缓存局部性 好:连续内存,命中率高,常数因子小 差:指针跳转 + 频繁 new/delete,易产生内存碎片
典型适用场景 容量可预估、追求速度:表达式求值、括号匹配、单调栈、递归模拟、DFS 容量完全无法预估、元素体积大、数量剧烈波动:通用容器、解析器、符号表
实现难度 低(只需当心 ++ / -- 的先后顺序) 高(要处理指针和 new / delete)
一句话选型 能预估容量就用顺序栈,预估不了再用链栈。 做题时也可以直接用 STL 的 std::stack,不用自己写 —— 本讲后面的应用大多就是这么做的。
// stl_stack_demo.cpp —— 标准库的 std::stack:做题时可以直接拿来用
// 记住三点:① 接口是 push / pop / top / empty / size;
//          ② pop() 不返回值,要先用 top() 取出栈顶再 pop();
//          ③ 不能遍历、不能下标访问,只能看栈顶。
#include <bits/stdc++.h>
using namespace std;

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

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

3.5 经典应用一:括号匹配

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

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

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

算法描述只有五行:

  1. 遇到左括号 ( [ {:入栈。
  2. 遇到右括号 ) ] }:若栈空,说明这个右括号多余,失败;
  3. 否则看栈顶:与当前右括号类型相同则弹出(配对成功),类型不同则失败。
  4. 扫描结束后再检查栈:栈空 → 匹配成功;栈非空 → 有左括号没被配对,失败。
  5. 其它字符(字母、数字、运算符、空白)一律跳过 —— 括号匹配只关心括号。
输入串 "{ [ ( ) ] }" 的完整扫描过程(栈底在左,栈顶在右) 步骤 当前字符 动作 栈内容(左 = 栈底,右 = 栈顶) 1 { 左括号 → 入栈 { 2 [ 左括号 → 入栈 { [ 3 ( 左括号 → 入栈 { [ ( 4 ) 与栈顶 ( 同类 → 弹出 { [ 5 ] 与栈顶 [ 同类 → 弹出 { 6 } 与栈顶 { 同类 → 弹出 (空栈) 扫描结束时栈为空 → 匹配成功;若栈非空(如 "(()")或有类型冲突(如 "([)]")则失败
图 3-5 括号匹配的逐步扫描:左括号入栈「记账」,右括号与栈顶「销账」

3.5.2 三种失败情形

失败情形例子在哪一步被发现判定条件
右括号多余 ())、)( 扫描到多余的右括号那一瞬间 遇到右括号,但栈已空
左括号多余 (()、(( 整个串扫描完之后 循环结束,但栈非空
类型不匹配 ([)]、{(}) 扫描到与栈顶不同类的右括号时 栈非空,但栈顶与当前右括号不是一对
最容易被忽略的是第二种 前两种失败中,「右括号多余」在循环里就能发现,很多同学写完循环就 return true 了 —— 于是 (() 被误判为匹配成功。循环结束后必须再判一次栈空,这是本题唯一的「隐藏考点」。 另外注意:([)] 的左右括号总数是相等的,但嵌套交叉了,所以仍然失败 —— 这也说明「数括号个数」这种偷懒做法是错的(顺便说,那种做法还会被字符串里的字符字面量、注释骗到)。

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

3.5.3 C++ 完整实现

第一份实现是「完整版」:除了判断对错,还报出失败的位置和原因(哪个括号多了、哪一对类型不配)。 第二份是「考试版」:只返回 bool,十几行手写就能默出来。两份都值得会。

// bracket_match.cpp —— 括号匹配(完整版):支持 () [] {},返回失败位置与原因
#include <bits/stdc++.h>
using namespace std;

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

void Test(const string& s) {
    string r = CheckBrackets(s);
    cout << (r.empty() ? "[通过] " : "[失败] ") << '"' << s << '"';
    if (!r.empty()) cout << "   → " << r;
    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 <bits/stdc++.h>
using namespace std;

bool Match(const char* str) {
    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)
        cout << (Match(s) ? "匹配   " : "不匹配 ") << s << '\n';
    return 0;
}
考点与复杂度 ① 时间 O(n):每个字符恰好被处理一次,每个括号最多进栈一次、出栈一次; ② 空间 O(n):最坏情况(如 (((((()栈里同时存着 n 个左括号; ③ 空串、无括号串都算匹配;④ 必须处理「循环结束后判栈空」这一条。 常见变体:「最长有效括号」「删除最少括号使串合法」都是它的近亲。

3.6 经典应用二:进制转换

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

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

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

156 转二进制:不断除以 2 156 ÷ 2 = 78 余 0 78 ÷ 2 = 39 余 0 39 ÷ 2 = 19 余 1 19 ÷ 2 = 9 余 1 9 ÷ 2 = 4 余 1 4 ÷ 2 = 2 余 0 2 ÷ 2 = 1 余 0 1 ÷ 2 = 0 余 1 余数从下往上读 结果:156 = ( 10011100 )₂ 共 8 位 最先得到的余数是低位,最后得到的才是高位 156 转十六进制:除以 16 156 ÷ 16 = 9 余 12 → C 9 ÷ 16 = 0 余 9 只用 2 步就够了 结果:156 = ( 9C )₁₆ 进制越大,位数越短: 156 = 10011100₂ = 234₈ = 9C₁₆ 算法完全一样,只把除数换成 base; 余数 10~15 用 A~F 表示即可
图 3-6 短除法 + 栈:余数依次入栈,出栈时自然变成「高位在前」

手动验算 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 <bits/stdc++.h>
using namespace std;

const char DIGIT[] = "0123456789ABCDEF";
char st[70];      // 栈:存余数对应的字符(64 位整数转二进制最多 64 位,开 70 够用)
int top = -1;     // 约定 A:top 指向栈顶元素,top == -1 表示空栈

// 把 n 转成 base 进制;base 不在 2~16 之间时返回空串(用返回值报告错误)
string ToBase(long long n, int base) {
    if (base < 2 || base > 16) return "";

    bool neg = (n < 0);
    // 取绝对值:先 -(n+1) 再 +1,避免 n == LLONG_MIN 时取负溢出
    unsigned long long x = neg ? (unsigned long long)(-(n + 1)) + 1 : (unsigned long long)n;

    top = -1;
    if (x == 0) st[++top] = '0';               // 0 要特判,否则循环一次都不执行
    while (x > 0) {
        st[++top] = DIGIT[x % base];           // 低位先入栈
        x /= base;
    }

    string out = neg ? "-" : "";
    while (top >= 0) out += st[top--];         // 出栈 = 高位 → 低位
    return out;
}

int main() {
    long long tests[] = {156, 0, 255, -156, 1000000000LL};
    for (long long v : tests) {
        cout << v << " → 二进制 " << ToBase(v, 2)
             << " | 八进制 " << ToBase(v, 8)
             << " | 十六进制 " << ToBase(v, 16) << '\n';
    }
    if (ToBase(10, 20) == "") cout << "非法进制 20 → 返回空串\n";
    return 0;
}
易错:0 与负数 ① 0 是最大的坑:while (x > 0) 一次都不执行,栈是空的,输出就成了空字符串。 必须特判「若 x == 0 则直接返回 "0"」(上面的代码用「先 push 一个 '0'」处理)。 ② 负数要先取绝对值、最后补负号;但 -LLONG_MIN 会溢出,所以要用 -(n + 1) + 1 这种写法(或者转成 unsigned long long 再取负)。 ③ 余数 10~15 必须映射成 A~F,别指望 to_string 帮你。
反过来:任意进制 → 十进制(霍纳法则) 反向转换不需要栈:从左到右逐位扫描,ans = ans * base + digit,一遍就够 (这就是秦九韶 / 霍纳法则 Horner's rule)。栈只在「低位先算出来、但输出要高位在前」时才需要。 这一点常被拿来出题:问「进制转换的哪一步需要栈」,答案就是「十进制转其他进制时倒序输出余数」。

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)。 三种写法里操作数的相对顺序完全一样,变的只是运算符的位置 —— 这一点务必先记住, 它是所有转换方法的基础。

表达式写法上面例子的结果怎么读
中缀 infix 操作数 运算符 操作数 3 + 4 * 2 - ( 1 + 5 ) ^ 2 / 3 人读的方式,需要优先级与括号
前缀 prefix / 波兰式 运算符 操作数 操作数 - + 3 * 4 2 / ^ + 1 5 2 3 从右往左扫;运算符作用于它右边紧邻的两个操作数
后缀 postfix / 逆波兰式 操作数 操作数 运算符 3 4 2 * + 1 5 + 2 ^ 3 / - 从左往右扫;运算符作用于它左边紧邻的两个操作数

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

− + / 3 * ^ 3 4 2 + 2 1 5 表达式树 叶子 = 操作数,内部结点 = 运算符 前序遍历(根→左→右)= 前缀式 - + 3 * 4 2 / ^ + 1 5 2 3 后序遍历(左→右→根)= 后缀式 3 4 2 * + 1 5 + 2 ^ 3 / -
图 3-7 表达式树:前序 = 前缀式,后序 = 后缀式,中序 = 中缀式(需要重新补括号)

手推方法一:加括号法(最快,考试首选)

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

步骤式子(逐步加括号)说明
原始3 + 4 * 2 - ( 1 + 5 ) ^ 2 / 3括号本来就有一对,保留
① 先算 ^3 + 4 * 2 - ( ( 1 + 5 ) ^ 2 ) / 3幂优先级最高
② 再算 *3 + ( 4 * 2 ) - ( ( 1 + 5 ) ^ 2 ) / 3乘除高于加减
③ 再算 /3 + ( 4 * 2 ) - ( ( ( 1 + 5 ) ^ 2 ) / 3 )除与乘同级,左侧先算
④ 再算 +( 3 + ( 4 * 2 ) ) - ( ( ( 1 + 5 ) ^ 2 ) / 3 )加在减左边,所以先算加
⑤ 最后 -( ( 3 + ( 4 * 2 ) ) - ( ( ( 1 + 5 ) ^ 2 ) / 3 ) )整个式子被一层括号包住
后缀:运算符移到右括号后3 4 2 * + 1 5 + 2 ^ 3 / -去掉括号即得后缀式
前缀:运算符移到左括号前- + 3 * 4 2 / ^ + 1 5 2 3去掉括号即得前缀式

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

手推方法二:栈扫描法(程序实现的方法)

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

步读入运算符栈(底 → 顶)输出序列依据
13(空)3操作数直接输出
2++3栈空,直接入栈
34+3 4操作数直接输出
4*+ *3 4isp(+) = 3 < icp(*) = 4 → 不弹,入栈
52+ *3 4 2操作数直接输出
6--3 4 2 * +isp(*) = 5 ≥ 2 弹 *;isp(+) = 3 ≥ 2 弹 +;再入栈
7(- (3 4 2 * +左括号直接入栈
81- (3 4 2 * + 1操作数直接输出
9+- ( +3 4 2 * + 1isp( ( ) = 1 < icp(+) = 2 → 入栈(左括号挡住了)
105- ( +3 4 2 * + 1 5操作数直接输出
11)-3 4 2 * + 1 5 +弹出到 ( 为止,( 出栈丢弃
12^- ^3 4 2 * + 1 5 +isp(−) = 3 < icp(^) = 7 → 入栈
132- ^3 4 2 * + 1 5 + 2操作数直接输出
14/- /3 4 2 * + 1 5 + 2 ^isp(^) = 6 ≥ 4 弹 ^;isp(−) = 3 < 4 → 入栈
153- /3 4 2 * + 1 5 + 2 ^ 3操作数直接输出
16扫描结束(空)3 4 2 * + 1 5 + 2 ^ 3 / -把栈里剩下的 /、- 依次弹出

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

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

运算符栈内优先级 isp
(in-stack priority)
栈外优先级 icp
(in-coming priority)
结合性说明
+ -32左结合icp = isp − 1:等优先级时栈顶先出,保证左结合
* /54左结合同上,且整体高于加减
^(幂)67右结合icp = isp + 1:等优先级时栈顶不弹,保证右结合
(16—栈内最低(谁也弹不走它),栈外极高(进栈后挡住下面所有运算符)
)———特判:不停弹出并输出,直到遇见 (,再把 ( 弹出丢弃
算法四句话
  1. 操作数:直接追加到输出序列(操作数之间不比较优先级)。
  2. 运算符 op:while (栈非空 && isp(栈顶) >= icp(op)) 弹出栈顶并输出; 然后把 op 入栈。
  3. 左括号:直接入栈。右括号:弹出并输出直到栈顶是左括号,再把左括号弹出丢弃。
  4. 扫描结束:把栈里剩余的运算符全部弹出输出(漏掉这一步是最常见的错误)。

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

考点:为什么两套优先级? 考研题常见问法:「中缀转后缀时,( 的栈内优先级为什么最低、栈外优先级为什么最高?」 答:栈内最低 → 任何栈外运算符都不会把它弹出去(保证括号内的运算先算完); 栈外最高 → 它一进栈就压在下面所有运算符之上,形成一道「隔离墙」。 另外注意:同一个运算符的 isp 与 icp 一般不相等,这个「不等」正是结合性的编码方式。
易错:同级运算符没有先弹 左结合全靠「同级时栈顶先弹」。本节的两张表里 isp 比 icp 大 1(如 isp(+) = 3、icp(+) = 2),所以弹出条件写 >= 还是 > 都会弹; 但如果只用一套优先级(isp = icp,3.7.5 双栈法里的 priority() 就是这样),弹出条件就必须写 >=。 写成 > 会让同级运算符留在栈里, 于是 a-b+c 被算成 a-(b+c),8/4/2 被算成 8/(4/2)=4(正确结果是 1)。 这类 bug 在测试用例里很容易蒙混过关(a+b+c 这种同运算符加法恰好不受影响), 一定要用 减法与除法去测。

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

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

// infix_to_postfix.cpp —— 中缀表达式转后缀表达式
// 支持:多位数、小数、+ - * / ^ 与圆括号;^ 为右结合(icp > isp)
#include <bits/stdc++.h>
using namespace std;

/* 栈内优先级:运算符已经在栈里时的优先级 */
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:连续的数字与小数点算一个操作数,其余每个字符算一个运算符 */
vector<string> Tokenize(const string& s) {
    vector<string> out;
    for (size_t i = 0; i < s.size(); ) {
        char c = s[i];
        if (c == ' ') { ++i; continue; }
        if (isdigit(c) || c == '.') {
            string num;
            while (i < s.size() && (isdigit(s[i]) || s[i] == '.')) num += s[i++];
            out.push_back(num);
        } else {
            out.push_back(string(1, c));
            ++i;
        }
    }
    return out;
}
bool IsNumber(const string& t) {
    return !t.empty() && (isdigit(t[0]) || t[0] == '.');
}

/* 转换成功返回 true,后缀式放进 out;表达式有错(括号不配对、非法字符)返回 false */
bool InfixToPostfix(const string& expr, string& out) {
    vector<string> tk = Tokenize(expr);
    stack<char> ops;                          // 运算符栈
    out = "";                                 // 输出序列(后缀式)

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

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"
    };
    string res;
    for (const char* s : tests) {
        InfixToPostfix(s, res);
        cout << s << "\n   → " << res << "\n";
    }
    if (!InfixToPostfix("( 1 + 2", res)) cout << "( 1 + 2 → 括号不匹配,返回 false\n";
    return 0;
}
自测:跑一遍这三组数据 ① 2 ^ 3 ^ 2 应输出 2 3 2 ^ ^(右结合;若你得到 2 3 ^ 2 ^,说明 ^ 的 icp/isp 写反了); ② 8 - 4 - 2 应输出 8 4 - 2 -(左结合;若得到 8 4 2 - -,说明同级的 - 没有先弹:isp 没比 icp 大,或者只用一套优先级却写成了 >); ③ 1.5 + 22 * ( 3 - 0.5 ) 应输出 1.5 22 3 0.5 - * +(多位数与小数不能被拆散) —— 这三组数据恰好覆盖了右结合、左结合、词法切分三个最容易错的地方。

3.7.4 后缀表达式求值

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

最容易错的一步:谁减谁? 弹出两个操作数时,先弹出的是「右操作数」,后弹出的是「左操作数」。 对 +、* 这两种可交换的运算,写反了看不出来; 但对 -、/、^ 立刻就错:3 4 - 是 3-4 = -1, 写成 4-3 = 1 就全毁了。正确写法永远是 double b = st.top(); st.pop(); double a = st.top(); st.pop(); 然后 a op b。请把「先出栈的是右边那个」这句话念三遍。

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

步读入操作数栈(底 → 顶)动作
133压栈
243 4压栈
323 4 2压栈
4*3 8弹 2、4 → 4*2=8 压栈
5+11弹 8、3 → 3+8=11 压栈
6111 1压栈
7511 1 5压栈
8+11 6弹 5、1 → 1+5=6 压栈
9211 6 2压栈
10^11 36弹 2、6 → 6^2=36 压栈
11311 36 3压栈
12/11 12弹 3、36 → 36/3=12 压栈
13--1弹 12、11 → 11-12=-1 压栈(左 − 右)
14结束-1栈中只剩一个数 → 答案 = −1

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

// postfix_eval.cpp —— 后缀表达式求值:一个操作数栈 + 一次线性扫描
// 支持多位数(如 22、100)与小数(如 1.5、0.25)
#include <bits/stdc++.h>
using namespace std;

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

/* 求值成功返回 true,结果放进 res;后缀式非法(操作数不够、除数为 0、非法运算符)返回 false */
bool EvalPostfix(const string& expr, double& res) {
    vector<string> tk = Tokenize(expr);
    stack<double> st;                         // 操作数栈
    for (const string& t : tk) {
        if (IsNumber(t)) {
            st.push(stod(t));                 // 多位数 / 小数一次读入
            continue;
        }
        if (st.size() < 2) return false;      // 操作数不足
        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) return false;     // 除数为 0
                v = a / b; break;
            case '^': v = pow(a, b); break;
            default:  return false;           // 非法运算符
        }
        st.push(v);                           // 结果压回栈中
    }
    if (st.size() != 1) return false;         // 扫描结束时栈里应该恰好剩一个数
    res = st.top();
    return true;
}

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(谁减谁)
    };
    double res;
    for (const char* s : tests) {
        EvalPostfix(s, res);
        printf("%-28s = %g\n", s, res);
    }
    if (!EvalPostfix("1 +", res)) printf("1 + → 操作数不足,返回 false\n");
    return 0;
}
本节从略 双栈法从略:表达式只要求掌握「中缀转后缀 → 后缀求值」这一条完整链路。

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

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

3.8.1 函数调用栈与栈帧

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

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

阶乘的递归写法 long long f(int n) { if (n <= 1) return 1; return n * f(n - 1); } ↓ 递推(进入):每调用一层,   就压入一个栈帧 ↑ 回归(返回):弹出栈帧,   用栈帧里的返回地址跳回去 调用栈的深度 = n → 空间复杂度 O(n) 调用栈(栈顶在下,越往下越早调用) f(4) n = 4 返回地址:main 的第 12 行;待算 4 × f(3) f(3) n = 3 返回地址:f(4) 的 return 行;待算 3 × f(2) f(2) n = 2 返回地址:f(3) 的 return 行;待算 2 × f(1) f(1) n = 1 → 命中递归出口 return 1 (不再产生新的栈帧) 递推 回 归 1 → 2 → 6 → 24
图 3-8 递归调用栈:递推阶段层层压栈,命中出口后逐层弹栈并回代结果

3.8.2 两个经典递归:阶乘、斐波那契

// recursion_demo.cpp —— 阶乘 / 斐波那契 / 汉诺塔:递归的三种典型形状
#include <bits/stdc++.h>
using namespace std;

/* ① 阶乘:线性递归。递归深度 = 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, 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);
}

int main() {
    cout << "5! 递归 = " << FactRec(5) << ",迭代 = " << FactIter(5) << '\n';
    cout << "Fib(10) 朴素递归 = " << FibRec(10) << '\n';
    vector<long long> memo(51, -1);
    cout << "Fib(50) 记忆化 = " << FibMemo(50, memo)
              << "(朴素递归要算约 200 亿次,根本跑不完)\n";
    return 0;
}
考点:递归的复杂度怎么算 ① 时间:写出递归式再解。阶乘 T(n) = T(n-1) + O(1) = O(n); 朴素斐波那契 T(n) = T(n-1) + T(n-2) + O(1) = O(2^n) (记忆化后降到 O(n))。 ② 空间:等于递归深度(不是调用次数!)。递归的空间是 O(递归深度) —— 递推到底后栈帧逐层弹掉,同一时刻栈里最多 n 层。这是最常见的送分/送命题。
本节从略 用显式栈改写递归从略:树和图的遍历统一用递归实现;深度过大时再查显式栈写法。
本节从略 递归与显式栈的对比从略:本轮只要求会写递归,不要求非递归。

3.9 经典应用四:迷宫求解(回溯)

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

算法描述(方向顺序固定为「上、右、下、左」):

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

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

S × E ■ 通路 ■ 死路(已出栈回退) ■ 入口 S ■ 出口 E □ 没走到 从 S(1,1) 先向右试到 (1,2):四面不通 → 出栈回退,再改试向下,最终到达 E(4,6) 栈的变化(栈顶在上) (1,2) ← 死路 (1,1) S ① 四面不通,准备回退 Pop (1,1) S ② 弹出 (1,2) 后,回到 (1,1)   改试下一个方向:向下 栈里始终是「当前这条路径」
图 3-9 迷宫求解:栈里保存当前路径,走进死路就出栈回退(回溯)
// maze_stack.cpp —— 迷宫求解:栈式回溯(本质是在图上做深度优先搜索 DFS)
#include <bits/stdc++.h>
using namespace std;

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(vector<Pos>& path) {
    int mark[R][C] = {0};                  // 是否已经进过栈(避免原地兜圈子)
    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(); }
            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 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'; cout << g[r] << '\n'; }
}

int main() {
    vector<Pos> path;
    if (SolveMaze(path)) {
        cout << "找到通路,共 " << path.size() << " 个格子:\n";
        PrintMaze(path);
        cout << "路径坐标:";
        for (size_t i = 0; i < path.size(); ++i)
            cout << '(' << path[i].r << ',' << path[i].c << ')' << (i + 1 < path.size() ? " → " : "");
        cout << '\n';
    } else {
        cout << "迷宫无解\n";
    }
    return 0;
}
考点:迷宫与回溯法的关系 ① 迷宫求解本质是图的深度优先搜索(DFS):每个可走格子是顶点,相邻可走关系是边; ② 用栈实现的 DFS 就是「栈式回溯」,第 08 讲会给出通用的图 DFS 模板,代码骨架与此完全一致; ③ 复杂度:每个格子最多进栈一次、出栈一次,每次检查 4 个方向, 所以时间 O(4·m·n) = O(m·n),空间 O(m·n); ④ 若要求最短路径,DFS 不行(它找到的只是「一条」路),必须换成队列 + BFS(第 04 讲); ⑤ 若要求所有路径,则要在出栈时把 mark 清回 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] 都是比它们更优的候选 —— 这就是可以「扔掉历史」的严格理由。

iA[i]弹出(并记录 ans)栈(底 → 顶)ans 现状
02—[0]· · · · · · ·
11—(A[0]=2 > 1,不弹)[0, 1]· · · · · · ·
25弹出 1、0[2]5 5 · · · · ·
36弹出 2[3]5 5 6 · · · ·
42—(A[3]=6 > 2)[3, 4]5 5 6 · · · ·
53弹出 4[3, 5]5 5 6 · 3 · ·
61—(A[5]=3 > 1)[3, 5, 6]5 5 6 · 3 · ·
结束—栈中剩余 3、5、6 右边没有更大元素[]5 5 6 −1 3 −1 −1
① 数组 A(下标 0 ~ 6) 2 1 5 6 2 3 1 012 3456 ② 答案 ans[i]:右边第一个更大的元素 5 5 6 −1 3 −1 −1 不变式:栈里存的是「还没找到答案」的下标,且对应的值从栈底到栈顶单调不增 while (栈非空 && A[栈顶] < A[i]) { ans[栈顶] = A[i]; 弹出; } 再 push(i) 每个下标最多进栈一次、出栈一次 → 总操作 ≤ 2n → 时间 O(n),空间 O(n) 扫描结束时栈里剩下的下标,右边都不存在更大的元素,答案就是 −1
图 3-10 单调栈求「下一个更大元素」:新元素一出现就结算掉栈里所有比它小的位置

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

// monotonic_stack.cpp —— 单调栈:下一个更大元素
#include <bits/stdc++.h>
using namespace std;

/* ① 下一个更大元素:对每个 i,求右边第一个比 A[i] 大的值,不存在记 -1 */
vector<int> NextGreater(const vector<int>& A) {
    int n = (int)(A.size());
    vector<int> ans(n, -1);
    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
}

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

    return 0;
}
本节从略 直方图最大矩形从略:单调栈只要求掌握「下一个更大元素」这一种用法。