1. C++ stack 的基础概念
1.1 栈的定义与性质
栈（stack）是一种后进先出（LIFO）的数据结构，在软件工程中常用于实现回溯、表达式求值、以及局部状态保存等场景。作为一种数据结构，栈只暴露少量操作接口，核心操作包括入栈 push、出栈 pop、查看栈顶 top，以及判断栈空的 empty。这些操作在最坏情况下都保持 Nearly 常数时间复杂度，使其在算法实现中具有很好的表现。
在 C++ 中，std::stack 是一个容器适配器，它把底层的容器包装成栈的接口，因此你可以通过不同的底层容器来权衡性能与特性。需要注意的是，栈的实现对外暴露的只是一组有限的操作，不提供遍历容器的接口，这也是栈的典型封装风格之一。
1.2 栈的基本操作
使用栈时，最常见的操作包括 push 推入元素、top 获取栈顶元素、pop 弹出栈顶元素、以及 empty/size 等辅助操作。需要注意的是，在调用 top 或 pop 之前，通常应通过 empty 检查栈是否为空，以避免运行时错误。
下面给出一个最简的使用示例，演示如何将元素依次入栈、再逐个弹出并读取栈顶值。该示例强调了栈的后进先出特性以及基本操作的顺序性。
#include <stack>
#include <iostream>
int main() {
std::stack<int> s;
s.push(10);
s.push(20);
s.push(30);
while (!s.empty()) {
// 取栈顶
int val = s.top();
std::cout << val << std::endl;
// 出栈
s.pop();
}
return 0;
}
2. std::stack 容器适配器的使用
2.1 基本用法
标准库中的 std::stack 是一个容器适配器，默认底层容器为 std::deque，也可以显式指定底层容器。栈提供的是一个对底层容器的封装接口，确保了 插入和删除操作在常数时间内完成，并且通过 top 提供对栈顶元素的只读访问（可读写）。
在实际编码中，了解底层容器的特性对性能有直接影响。若你的场景需要连续内存（如缓存的局部性较好），可以将底层容器改为 std::vector；若你需要更稳定的增长策略（避免可能的再分配），std::deque 是更常见的选择。然而，std::stack 不支持遍历，若需要遍历，需要将内容拷贝到其他容器中。
#include <stack>
#include <string>
#include <iostream>
int main() {
std::stack<std::string> st;
st.push("apple");
st.push("banana");
std::cout << "Top: " << st.top() << std::endl; // banana
st.pop();
std::cout << "Top after pop: " << st.top() << std::endl; // apple
return 0;
}
2.2 底层容器选择
模板定义为 std::stack<T, Container>，其中 Container 必须满足对 push_back、pop_back、back、empty、size 的支持。常用的底层容器及其权衡如下：std::deque 提供双端队列式的高效 push_back/pop_back，适合通用场景；std::vector 在连续内存中有更好的缓存友好性，但扩容时可能触发重新分配；std::list 提供稳定的迭代能力与最小的移动成本，但对栈而言往往没有优势，因为它不具备随机访问和高缓存命中率。
下面的示例展示了如何显式指定底层容器为 std::vector，以便在某些场景下获得更好的内存局部性。
#include <stack>
#include <vector>
#include <iostream>
int main() {
// 使用 vector 作为底层容器
std::stack<int, std::vector<int>> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty()) {
std::cout << st.top() << " ";
st.pop();
}
std::cout << std::endl;
return 0;
}
3. 从基础到实战：栈在算法与数据结构中的应用
3.1 深度优先搜索（DFS）中的栈应用
在图算法中，栈可以替代递归实现 DFS，从而避免深度递归带来的栈溢出风险，并且便于对操作顺序进行控制。采用显式栈的迭代 DFS，通常先将起点入栈，再在循环中弹出并将未访问的邻接点入栈，直到栈为空。
下面的示例演示了一个简单的迭代 DFS，使用 std::stack 来管理待访问的顶点集合。
#include <vector>
#include <stack>
#include <iostream>
void dfs(int n, const std::vector<std::vector<int>>>> &adj) {
std::vector<bool> vis(n, false);
std::stack<int> st;
st.push(0);
while (!st.empty()) {
int u = st.top();
st.pop();
if (vis[u]) continue;
vis[u] = true;
// 处理顶点 u 的逻辑
for (int v : adj[u]) {
if (!vis[v]) st.push(v);
}
}
}
int main() {
std::vector<std::vector<int>> adj = { {1,2}, {3}, {3}, {} };
dfs(4, adj);
return 0;
}
3.2 括号匹配与表达式处理
栈在括号匹配、表达式求值等场景中有广泛应用。对于一个表达式，只要遇到左括号就入栈，遇到右括号时就尝试与栈顶的左括号匹配，若匹配成功则继续，否则表示括号不配对。通过这种方式可以在一次遍历中完成判断，时间复杂度为 O(n)，空间复杂度取决于括号嵌套的深度。
下面是一个简单的括号匹配实现，支持三种括号类型：圆括号、花括号和方括号。
#include <string>
#include <stack>
#include <iostream>
bool isValid(const std::string& s) {
std::stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
char t = st.top(); st.pop();
if ((t == '(' && c != ')') || (t == '{' && c != '}') || (t == '[' && c != ']'))
return false;
}
}
return st.empty();
}
int main() {
std::cout << std::boolalpha << isValid("([]){}") << std::endl;
std::cout << isValid("(]") << std::endl;
return 0;
}
4. 实战技巧与注意事项
4.1 性能与异常处理
对 push/top/pop 等操作的时间复杂度通常是常数时间 (O(1))，但这取决于底层容器的实现。当底层容器为 std::vector 时，push 可能触发重新分配；而 std::deque 则通常提供更稳定的常数时间复杂度。 检查栈是否为空 再进行 top 或 pop，是避免运行时错误的基本实践。
在异常场景中，栈的操作如果抛出异常，应在应用层做好恢复或清理，并遵循 RAII 原则。以下示例展示了对空栈进行保护性操作，以及对 push 的异常处理思路。
#include <stack>
#include <iostream>
int main() {
std::stack<int> s;
if (!s.empty()) s.pop();
try {
s.push(42);
} catch (const std::exception& e) {
std::cerr << "Push failed: " << e.what() << std::endl;
}
return 0;
}
4.2 与现代 C++ 的结合
在现代 C++ 项目中，std::stack 作为一个简单而强大的容器适配器，适合需求明确的栈场景。然而，因为它不支持直接遍历，若你需要检查或输出栈中的中间元素，通常的做法是将内容拷贝到一个可迭代的容器中，或在实现中将底层容器暴露为受保护成员并在受控的包装中使用。栈的封装性是其设计初衷之一，这也是它在代码结构中的合理选择。
