第 03 讲 栈及其经典应用
栈是「后进先出」的受限线性表,也是整个数据结构课程里性价比最高的一章: 它的结构简单到只有一句话,却能解决括号匹配、进制转换、表达式求值、递归消除、迷宫回溯、单调栈优化这一长串经典问题。 本讲把栈的三种存储实现讲透,再用可单步、可播放的动画把每个应用的执行过程拆开给你看。
- 概念层:栈的定义、LIFO 特性、为什么必须「只在栈顶操作」,栈顶 / 栈底 / 空栈 / 上溢 / 下溢五个术语,以及栈的 ADT 七个操作。
- 存储层:顺序栈(数组 +
top,含top的两种约定)、共享栈(两个栈抢一个数组)、链栈(用单链表实现),三者放在一张表里对比。 - 应用层:括号匹配 → 进制转换 → 表达式求值(中缀转后缀 / 后缀求值) → 栈与递归 → 迷宫回溯 → 单调栈(下一个更大元素)。
- 动画层:6 个交互动画,全部支持「▶ 播放 / ◀ 上一步 / 下一步 ▶ / ⏮ 重来 / ⏭ 末帧」与速度调节,建议逐帧对着说明栏看。
- 代码层:18 段可直接编译运行的 C++ 代码,统一用竞赛写法(全局数组 + 普通函数,出错用返回值报告),都带
main测试。
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,根本没有元素可取。 上溢是空间不够,下溢是逻辑错误 —— 前者可以靠扩容或换链栈避免,后者只能靠程序员自己检查。
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 放到栈顶,成为新的栈顶 | 栈不满,否则上溢,返回 false | O(1) |
Pop(e) | 出栈:删除栈顶元素并用 e 带回 | 栈不空,否则下溢,返回 false | O(1) |
GetTop(e) | 取栈顶:用 e 带回,只读,不删除 | 栈不空 | O(1) |
ClearStack() | 清空:回到初始空栈状态 | — | O(1)(顺序栈置 top);O(n)(链栈逐个 delete) |
StackLength() | 求长度:返回元素个数 | — | O(1)(链栈用一个计数器 cnt 记着) |
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(本身就是长度)
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 左移;
只有当两个栈顶迎面撞上、中间一个空位都不剩时,才算「整个数组满了」。
也就是说,只有当两个栈的元素个数加起来占满整个数组时才会上溢:一个栈用得少,另一个栈就能多用,
不再被死死限制在「各自一半」。
/* ==========================================================================
共享栈 —— 两个栈共用一个数组,从两端往中间长
--------------------------------------------------------------------------
场景:需要两个栈,但它们的容量此消彼长(一个用得多、另一个就用得少)。
如果各开一个定长数组,就得给两边都按最坏情况开,浪费一半空间。
共享栈的解法:数组两端各是一个栈的栈底,两个栈顶向中间生长。
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.3n | 0 号栈上溢(浪费 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、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 也会失败,但那不是栈本身的容量限制,
做题时不用考虑。
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) |
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 本质:右括号要找「最近的」左括号
从左到右扫描字符串,遇到左括号就意味着「欠了一笔账」,先记账; 遇到右括号就是「来还账」,它必须和最近一笔还没还的账抵消。 而「最近的未完成事项」正好就是栈顶 —— 这就是为什么必须用栈,而不能用队列: 队列是先进先出,还的会是最早的那笔账,嵌套结构立刻就错了。
算法描述只有五行:
- 遇到左括号
( [ {:入栈。 - 遇到右括号
) ] }:若栈空,说明这个右括号多余,失败; - 否则看栈顶:与当前右括号类型相同则弹出(配对成功),类型不同则失败。
- 扫描结束后再检查栈:栈空 → 匹配成功;栈非空 → 有左括号没被配对,失败。
- 其它字符(字母、数字、运算符、空白)一律跳过 —— 括号匹配只关心括号。
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 = 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 是最大的坑: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 + 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 节动画里演的完全是同一件事。建议你先自己在纸上推一遍,再用动画对答案。
| 步 | 读入 | 运算符栈(底 → 顶) | 输出序列 | 依据 |
|---|---|---|---|---|
| 1 | 3 | (空) | 3 | 操作数直接输出 |
| 2 | + | + | 3 | 栈空,直接入栈 |
| 3 | 4 | + | 3 4 | 操作数直接输出 |
| 4 | * | + * | 3 4 | isp(+) = 3 < icp(*) = 4 → 不弹,入栈 |
| 5 | 2 | + * | 3 4 2 | 操作数直接输出 |
| 6 | - | - | 3 4 2 * + | isp(*) = 5 ≥ 2 弹 *;isp(+) = 3 ≥ 2 弹 +;再入栈 |
| 7 | ( | - ( | 3 4 2 * + | 左括号直接入栈 |
| 8 | 1 | - ( | 3 4 2 * + 1 | 操作数直接输出 |
| 9 | + | - ( + | 3 4 2 * + 1 | isp( ( ) = 1 < icp(+) = 2 → 入栈(左括号挡住了) |
| 10 | 5 | - ( + | 3 4 2 * + 1 5 | 操作数直接输出 |
| 11 | ) | - | 3 4 2 * + 1 5 + | 弹出到 ( 为止,( 出栈丢弃 |
| 12 | ^ | - ^ | 3 4 2 * + 1 5 + | isp(−) = 3 < icp(^) = 7 → 入栈 |
| 13 | 2 | - ^ | 3 4 2 * + 1 5 + 2 | 操作数直接输出 |
| 14 | / | - / | 3 4 2 * + 1 5 + 2 ^ | isp(^) = 6 ≥ 4 弹 ^;isp(−) = 3 < 4 → 入栈 |
| 15 | 3 | - / | 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) | 结合性 | 说明 |
|---|---|---|---|---|
+ - | 3 | 2 | 左结合 | icp = isp − 1:等优先级时栈顶先出,保证左结合 |
* / | 5 | 4 | 左结合 | 同上,且整体高于加减 |
^(幂) | 6 | 7 | 右结合 | icp = isp + 1:等优先级时栈顶不弹,保证右结合 |
( | 1 | 6 | — | 栈内最低(谁也弹不走它),栈外极高(进栈后挡住下面所有运算符) |
) | — | — | — | 特判:不停弹出并输出,直到遇见 (,再把 ( 弹出丢弃 |
- 操作数:直接追加到输出序列(操作数之间不比较优先级)。
- 运算符 op:
while (栈非空 && isp(栈顶) >= icp(op)) 弹出栈顶并输出;然后把 op 入栈。 - 左括号:直接入栈。右括号:弹出并输出直到栈顶是左括号,再把左括号弹出丢弃。
- 扫描结束:把栈里剩余的运算符全部弹出输出(漏掉这一步是最常见的错误)。
为什么左结合的运算符要满足 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,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 / -:
| 步 | 读入 | 操作数栈(底 → 顶) | 动作 |
|---|---|---|---|
| 1 | 3 | 3 | 压栈 |
| 2 | 4 | 3 4 | 压栈 |
| 3 | 2 | 3 4 2 | 压栈 |
| 4 | * | 3 8 | 弹 2、4 → 4*2=8 压栈 |
| 5 | + | 11 | 弹 8、3 → 3+8=11 压栈 |
| 6 | 1 | 11 1 | 压栈 |
| 7 | 5 | 11 1 5 | 压栈 |
| 8 | + | 11 6 | 弹 5、1 → 1+5=6 压栈 |
| 9 | 2 | 11 6 2 | 压栈 |
| 10 | ^ | 11 36 | 弹 2、6 → 6^2=36 压栈 |
| 11 | 3 | 11 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、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 <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 的显式栈一脉相承 —— 栈里存的就是「当前这条路径」,出栈就是「回退一步」。
算法描述(方向顺序固定为「上、右、下、左」):
- 把入口坐标压栈,并标记为「已走过」。
- 取栈顶位置,看它的四个方向里还有没有「没试过的、可走的、没走过的」格子: 有就压栈前进,并把该格标记为已走过;
- 四个方向都试完仍然走不通 → 出栈,回退一步(这就是回溯)。
- 栈顶到达终点 → 栈里从底到顶就是一条通路;栈空仍未到达 → 迷宫无解。
为什么每个格子「标记为已走过」之后就不用再清除?因为我们的目标是找一条路, 一个格子一旦证明「从这里走不到终点」,再走一次也是白走。 但如果题目要求「找出所有路径」或者「最短路径」,标记就必须在回退时撤销(恢复现场)—— 这正是回溯法与 DFS 的分水岭,也是回溯法的起点。
// 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;
}
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] 都是比它们更优的候选 —— 这就是可以「扔掉历史」的严格理由。
| i | A[i] | 弹出(并记录 ans) | 栈(底 → 顶) | ans 现状 |
|---|---|---|---|---|
| 0 | 2 | — | [0] | · · · · · · · |
| 1 | 1 | —(A[0]=2 > 1,不弹) | [0, 1] | · · · · · · · |
| 2 | 5 | 弹出 1、0 | [2] | 5 5 · · · · · |
| 3 | 6 | 弹出 2 | [3] | 5 5 6 · · · · |
| 4 | 2 | —(A[3]=6 > 2) | [3, 4] | 5 5 6 · · · · |
| 5 | 3 | 弹出 4 | [3, 5] | 5 5 6 · 3 · · |
| 6 | 1 | —(A[5]=3 > 1) | [3, 5, 6] | 5 5 6 · 3 · · |
| 结束 | — | 栈中剩余 3、5、6 右边没有更大元素 | [] | 5 5 6 −1 3 −1 −1 |
下面的动画把「数组指针、单调栈、答案数组」三者放在一起同步演示,并且会把每一次弹出都单独作为一帧,
方便你看清「谁被谁结算了」。注意栈里存的是下标而不是值 —— 因为我们需要把答案写回 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;
}