麦地

Back

1. 核心概念:LIFO#

1.1 基本定义#

#include <stack>
std::stack<int> st;
cpp

竞赛常用写法:

#include <bits/stdc++.h>
using namespace std;

stack<int> st;
cpp

LIFO: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;                 // 直接当栈使用,功能更灵活
cpp

3. 核心接口#

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() 返回 void
cpp

空栈调用 pop() 是未定义行为。

3.4 大小与判空#

st.size();
st.empty();
cpp

典型消费循环:

while (!st.empty()) {
    int x = st.top();
    st.pop();
    // 处理 x
}
cpp

3.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 本身没有 reserve
cpp

4.1 遍历会消费原栈#

while (!st.empty()) {
    cout << st.top() << ' ';
    st.pop();
}
cpp

如果需要保留原栈,先复制:

auto tmp = st; // O(n) 拷贝
while (!tmp.empty()) {
    cout << tmp.top() << ' ';
    tmp.pop();
}
cpp

4.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;
cpp

5.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. 应用一:括号匹配#

每种左括号入栈;遇到右括号时检查栈顶是否是对应左括号。

时间 O(n),空间 O(n)。

关键点:

  1. 右括号到来时先检查空栈。
  2. 类型必须匹配,不能只检查非空。
  3. 最后栈为空才说明全部匹配。
  4. 若输入只含一种括号,也可以用计数器,但不能处理嵌套类型匹配。

8. 应用二:显式 DFS#

8.1 基本模板#

时间复杂度通常为 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);
    }
}
cpp

8.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 作为哨兵:

弹出高度 height 时:

  • 当前下标 i 是右侧第一个更矮位置。
  • 弹出后的栈顶是左侧最近更矮位置。
  • 可扩展宽度为 i-left-1。

总时间 O(n)。注意面积可能溢出 int,应使用 long long。


11. 其他常见应用#

11.1 撤销与路径回溯#

vector<int> path;
path.push_back(u);
// 深入搜索
path.pop_back(); // 回到上一状态
cpp

11.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();
}
cpp

14.2 把 pop 当成返回值的函数#

// int x = st.pop(); // 错
int x = st.top();
st.pop();
cpp

14.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. 一页速记#

最终必须牢牢记住:

  1. stack 是 LIFO:最后入栈的元素最先出栈。
  2. top() 读取栈顶,pop() 删除栈顶且不返回值。
  3. 空栈不能 top/pop。
  4. stack 没有下标、迭代器、范围遍历和 clear。
  5. 显式 DFS 用 stack,无权最短路 BFS 用 queue。
  6. 单调栈通常存下标,每个元素至多入栈、出栈一次,总复杂度 O(n)。
  7. 需要遍历、reserve、clear 或下标访问时,直接用 vector 往往更方便。
Comment seems to stuck. Try to refresh?✨