1. 核心概念:LIFO#
1.1 基本定义#
#include <stack>
std::stack<int> st;cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
stack<int> st;cppLIFO:Last In, First Out,后进先出。
st.push(10);
st.push(20);
st.push(30);
cout << st.top(); // 30:最后入栈cpp出栈顺序为 30 -> 20 -> 10。
1.2 只能操作栈顶#
push()/emplace():在栈顶插入。top():读取栈顶。pop():删除栈顶。- 不能直接从栈底操作,也不能访问中间元素。
1.3 与函数调用栈的区别#
std::stack 是程序员显式创建的数据结构;函数调用栈是程序运行时管理函数调用、局部变量和返回地址的机制。递归过深导致的是函数调用栈溢出,与是否使用 std::stack 没有直接关系。显式 stack 可以把递归状态转移到堆上管理,常用于改写深递归。
2. stack 是容器适配器#
默认底层容器为 std::deque<T>:
stack<int> st;
// 近似等价于 stack<int, deque<int>> st;cpp也可以指定 vector 或 list:
stack<int, vector<int>> a;
stack<int, list<int>> b;cpp底层容器需要支持:
back()。push_back()。pop_back()。
因此 vector、deque、list 都可以。与 queue 不同,vector 可以作为 stack 的底层容器,因为 stack 不需要 pop_front()。
竞赛中常见两种选择:
stack<int> st; // 标准适配器,语义明确
stack<int, vector<int>> stv; // vector 作为底层
vector<int> v; // 直接当栈使用,功能更灵活cpp3. 核心接口#
3.1 入栈:push 与 emplace#
stack<int> st;
st.push(10);
int x = 20;
st.push(x); // 拷贝
st.push(move(x)); // 移动,之后不要依赖 x 的原值
st.emplace(30); // 直接构造cpp复合类型:
stack<pair<int, int>> stp;
stp.push({1, 2});
stp.emplace(3, 4);cpp对 int 等基本类型,push 和 emplace 通常没有性能区别。
3.2 读取栈顶:top#
cout << st.top();
st.top() = 100; // 可以修改栈顶元素cpp空栈调用 top() 是未定义行为。
3.3 出栈:pop#
st.pop(); // 删除栈顶,不返回元素cpp正确读取并出栈:
int x = st.top();
st.pop();cpp错误写法:
// int x = st.pop(); // 错:pop() 返回 voidcpp空栈调用 pop() 是未定义行为。
3.4 大小与判空#
st.size();
st.empty();cpp典型消费循环:
while (!st.empty()) {
int x = st.top();
st.pop();
// 处理 x
}cpp3.5 交换#
a.swap(b);
// 或 swap(a, b);cpp交换两个 stack 的内容,要求元素和底层容器类型匹配。
4. stack 没有哪些功能#
// st[0]; // 错误:没有随机访问
// st.begin(), st.end(); // 错误:没有公开迭代器
// for (int x : st) {} // 错误:不能直接范围遍历
// st.clear(); // 错误:没有 clear 成员
// st.front(); // 错误:front 属于 queue/deque 等
// st.reserve(n); // 错误:stack 本身没有 reservecpp4.1 遍历会消费原栈#
while (!st.empty()) {
cout << st.top() << ' ';
st.pop();
}cpp如果需要保留原栈,先复制:
auto tmp = st; // O(n) 拷贝
while (!tmp.empty()) {
cout << tmp.top() << ' ';
tmp.pop();
}cpp4.2 清空栈#
st = stack<int>();cpp或:
stack<int>().swap(st);cpp也可以:
while (!st.empty()) st.pop();cpp直接使用 vector 时则可以使用 v.clear(),更方便。
5. 元素类型与传参#
5.1 常见元素类型#
stack<int> a; // 节点、下标
stack<char> b; // 括号、运算符
stack<pair<int, int>> c; // 复合状态
stack<tuple<int,int,int>> d; // 三维状态
stack<string> e; // 路径、表达式片段cpp自定义结构体:
struct State {
int u;
int nextEdge;
int depth;
};
stack<State> st;cpp5.2 取出栈顶#
auto cur = st.top(); // 复制栈顶元素
st.pop();cpp对 int、pair 和小型 struct 通常足够高效。不要在 pop() 后继续使用之前保存的 top() 引用,因为元素已经被销毁。
5.3 函数传参#
void consume(stack<int> &st); // 修改原栈
void inspect(stack<int> st); // 使用独立副本,O(n) 拷贝cpp通常直接在算法函数内部创建局部 stack,避免不必要的复制。
6. 复杂度#
以常用底层容器 deque/vector 为例:
| 操作 | 时间复杂度 |
|---|---|
push() / emplace() |
均摊 O(1) |
pop() |
O(1) |
top() |
O(1) |
size() / empty() |
O(1) |
| 拷贝整个 stack | O(n) |
| 逐个 pop 清空 | O(n) |
swap |
通常 O(1) |
总成本还包括元素自身的构造、拷贝、移动和析构成本。stack 本身不提供 capacity() 或 reserve();直接使用 vector 时可以预留容量。
7. 应用一:括号匹配#
每种左括号入栈;遇到右括号时检查栈顶是否是对应左括号。
bool isValid(const string &s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else if (c == ')' || c == ']' || c == '}') {
if (st.empty()) return false;
char left = st.top();
st.pop();
if ((c == ')' && left != '(') ||
(c == ']' && left != '[') ||
(c == '}' && left != '{')) {
return false;
}
}
}
return st.empty();
}cpp时间 O(n),空间 O(n)。
关键点:
- 右括号到来时先检查空栈。
- 类型必须匹配,不能只检查非空。
- 最后栈为空才说明全部匹配。
- 若输入只含一种括号,也可以用计数器,但不能处理嵌套类型匹配。
8. 应用二:显式 DFS#
8.1 基本模板#
int s;
vector<char> vis(n + 1, false);
stack<int> st;
st.push(s);
vis[s] = true; // 入栈时标记
while (!st.empty()) {
int u = st.top();
st.pop();
// 处理 u
for (int v : g[u]) {
if (vis[v]) continue;
vis[v] = true;
st.push(v);
}
}cpp时间复杂度通常为 O(V+E)。
8.2 为什么入栈时标记#
若等出栈时再标记,同一节点可能被多个路径重复压入栈中,造成额外时间和空间消耗。入栈时标记可以保证每个节点至多入栈一次。
8.3 DFS 不保证最短路#
stack 产生深度优先搜索,它不能像 BFS 一样保证无权图首次访问即最短距离。求无权最短路应使用 queue。
8.4 控制访问顺序#
邻接点按 0、1、2 顺序入栈时,出栈顺序相反。若希望模拟递归的访问顺序,常按逆序压栈:
for (auto it = g[u].rbegin(); it != g[u].rend(); ++it) {
int v = *it;
if (!vis[v]) {
vis[v] = true;
st.push(v);
}
}cpp8.5 精确模拟递归需要更多状态#
只存节点编号的显式 DFS 能完成遍历,但不一定能精确还原“递归返回后从哪条边继续”的过程。需要后序处理、回溯或 Tarjan 等算法时,通常要保存 {u, nextEdge} 等帧状态:
struct Frame {
int u;
int edgeIndex;
};
stack<Frame> st;cpp不能只把递归函数里的所有节点简单换成 push/pop,而忽略递归的前后顺序。
9. 应用三:单调栈#
单调栈维护栈内元素的值或下标满足单调关系,常用于寻找左右两侧最近的更大/更小元素。
9.1 下一个更大元素#
vector<int> nge(n, -1);
stack<int> st; // 存下标
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] < a[i]) {
nge[st.top()] = i;
st.pop();
}
st.push(i);
}cpp核心思想:当前 a[i] 是某些尚未找到答案的下标的“第一个更大元素”。
每个下标最多入栈一次、出栈一次,因此总时间 O(n),而不是表面双重循环的 O(n^2)。
9.2 为什么通常存下标#
存下标既能通过 a[index] 得到值,又能计算距离和记录答案位置。只存值往往无法回答“在第几个位置”或“距离多远”。
9.3 大于与大于等于的区别#
a[st.top()] < a[i] // 找严格更大;相等元素不会触发弹出
a[st.top()] <= a[i] // 相等时也弹出,会改变相等元素的答案归属cpp使用 < 还是 <=,取决于题目要求“严格更大”还是“大于等于”,以及重复元素应取哪个位置。这是单调栈最常见的细节错误之一。
9.4 常见变体#
- 下一个更大 / 更小元素。
- 上一个更大 / 更小元素。
- 滑动窗口之外的最近边界问题。
- 柱状图最大矩形。
- 接雨水、股票跨度、去除 k 位数字等。
10. 应用四:柱状图最大矩形#
维护高度递增的下标栈,并在末尾加入高度 0 作为哨兵:
long long largestRectangle(vector<int> h) {
int n = h.size();
h.push_back(0); // 哨兵,强制清空栈
stack<int> st;
long long ans = 0;
for (int i = 0; i <= n; ++i) {
while (!st.empty() && h[st.top()] > h[i]) {
int height = h[st.top()];
st.pop();
int left = st.empty() ? -1 : st.top();
long long width = i - left - 1;
ans = max(ans, width * 1LL * height);
}
st.push(i);
}
return ans;
}cpp弹出高度 height 时:
- 当前下标
i是右侧第一个更矮位置。 - 弹出后的栈顶是左侧最近更矮位置。
- 可扩展宽度为
i-left-1。
总时间 O(n)。注意面积可能溢出 int,应使用 long long。
11. 其他常见应用#
11.1 撤销与路径回溯#
vector<int> path;
path.push_back(u);
// 深入搜索
path.pop_back(); // 回到上一状态cpp11.2 表达式求值与中缀转后缀#
- 操作数栈保存数值。
- 运算符栈保存运算符和括号。
- 根据优先级、结合性执行弹出和计算。
- 一元负号、多位数、错误输入需要额外处理。
11.3 最小栈#
在栈元素中同时保存当前最小值:
stack<pair<int,int>> st; // {value, 当前栈内最小值}
void push(int x) {
int mn = st.empty() ? x : min(x, st.top().second);
st.push({x, mn});
}
int getMin() {
return st.top().second; // 前提:栈非空
}cpp每次取最小值为 O(1),额外空间 O(n)。
11.4 用 string 或 vector 作字符栈#
string st;
st.push_back('(');
char c = st.back();
st.pop_back();cpp与 stack<char> 相比,string/vector 还能直接遍历、清空和查看所有元素。
12. 直接用 vector 代替 stack#
12.1 接口对应#
stack<T> |
vector<T> |
|---|---|
push(x) |
push_back(x) |
emplace(args...) |
emplace_back(args...) |
top() |
back() |
pop() |
pop_back() |
size() |
size() |
empty() |
empty() |
12.2 vector 的优势#
vector<int> st;
st.reserve(n); // 可以预留容量
st.clear(); // 可以直接清空
st[i]; // 可以查看栈内其他元素
for (int x : st) {} // 可以遍历,不改变内容cpp因此竞赛中很多人直接使用 vector 实现栈,尤其是:
- 已知最大规模,想减少扩容。
- 需要遍历或调试栈内所有元素。
- 单调栈需要查看下标或进行额外处理。
- 需要在算法结束后保留栈中剩余元素。
12.3 std::stack 的优势#
接口受限反而能表达意图:只允许栈顶操作,减少误用。若只需要 LIFO 且希望语义明确,标准 stack 很合适。
13. 容器选型#
| 需求 | 推荐容器 |
|---|---|
| 后进先出、显式 DFS、括号匹配 | stack 或 vector |
| 先进先出、BFS | queue |
| 两端插入删除、0-1 BFS、单调队列 | deque |
| 每次取最大/最小优先级 | priority_queue |
| 栈操作同时需要遍历、下标、reserve、clear | vector |
| 需要有序查询任意 key | set/map 等,不是 stack |
单调栈与单调队列不是一回事:
- 单调栈:只在一端维护,常用于最近更大/更小元素。
- 单调队列:两端都可能删除,常用于滑动窗口最值,使用 deque。
14. 高频错误与避坑清单#
14.1 空栈调用 top/pop#
if (!st.empty()) {
int x = st.top();
st.pop();
}cpp14.2 把 pop 当成返回值的函数#
// int x = st.pop(); // 错
int x = st.top();
st.pop();cpp14.3 使用 front/back 而不是 top#
std::stack 的栈顶接口是 top()。back() 是 vector/string/deque 等容器的接口。
14.4 pop 后继续使用旧引用#
// int &x = st.top();
// st.pop();
// cout << x; // 危险:引用已失效cpp应在 pop 前复制需要的值。
14.5 试图遍历 stack#
stack 没有迭代器和范围 for。消费式遍历会清空栈;需要保留内容就复制,需要频繁遍历就使用 vector。
14.6 误以为显式 DFS 等价于 BFS#
stack 是 LIFO,queue 是 FIFO。两者遍历顺序和最短路性质不同,不能直接互换。
14.7 单调栈误判为 O(n^2)#
虽然有嵌套 while,但每个元素最多入栈、出栈一次,总计 O(n)。
14.8 忽略重复元素与严格性#
< 和 <= 会影响重复元素的处理;左开右开区间、最近相等元素归属也要根据题意确定。
14.9 柱状图宽度与溢出#
弹出后计算宽度时使用当前栈顶作为左边界;面积使用 long long,末尾哨兵可以确保所有高度被处理。
15. 一页速记#
#include <stack>
stack<int> st; // 默认底层 deque<int>
stack<int, vector<int>> stv; // vector 底层
st.push(x); // 入栈
st.emplace(x); // 原位构造
st.top(); // 读取栈顶
st.pop(); // 删除栈顶,返回 void
st.size(); st.empty();
if (!st.empty()) {
int x = st.top();
st.pop();
}
stack<pair<int,int>> sp;
sp.push({u, state});
sp.emplace(u, state);
auto [a, b] = sp.top();
sp.pop();
st = stack<int>(); // 重置清空
// vector 替代
vector<int> v;
v.reserve(n);
v.push_back(x); // push
int x = v.back(); // top
v.pop_back(); // pop
v.clear();
// 显式 DFS
stack<int> dfs;
vis[s] = true;
dfs.push(s);
while (!dfs.empty()) {
int u = dfs.top(); dfs.pop();
for (int v : g[u]) {
if (vis[v]) continue;
vis[v] = true;
dfs.push(v);
}
}
// 下一个更大元素
vector<int> nge(n, -1);
stack<int> ms;
for (int i = 0; i < n; ++i) {
while (!ms.empty() && a[ms.top()] < a[i]) {
nge[ms.top()] = i;
ms.pop();
}
ms.push(i);
}cpp最终必须牢牢记住:
- stack 是 LIFO:最后入栈的元素最先出栈。
top()读取栈顶,pop()删除栈顶且不返回值。- 空栈不能
top/pop。 - stack 没有下标、迭代器、范围遍历和 clear。
- 显式 DFS 用 stack,无权最短路 BFS 用 queue。
- 单调栈通常存下标,每个元素至多入栈、出栈一次,总复杂度
O(n)。 - 需要遍历、reserve、clear 或下标访问时,直接用 vector 往往更方便。