C++ stack：数据结构的“叠盘子艺术”与“后进先出法则”
开篇小故事：厨房里的“盘子魔法”
想象你在厨房洗碗时，将盘子一个个叠放起来：
- 放入盘子：你只能将新盘子放在最顶端。
- 取出盘子：你只能从最顶端拿起盘子。
- 查看盘子：你只能看到最顶端的那个，无法直接抽出底层的盘子。
这种“叠盘子”的规则正是**栈（Stack）**的核心思想！在C++中，std::stack就像是一个智能叠盘架，帮你高效管理数据，严格遵守“后进先出（LIFO）”的法则。
一、stack是什么？
std::stack是C++标准模板库（STL）提供的容器适配器，基于其他容器（如deque或list）实现，专门用于LIFO操作。
- 核心特性：后进先出（Last In, First Out）。
- 受限操作：只能访问、添加或移除顶部的元素。
- 高效操作：
push（入栈）、pop（出栈）、top（查看栈顶）的时间复杂度均为O(1)。
与数组/链表的对比
| 操作 | 数组/链表 | stack |
|---|---|---|
| 插入位置 | 任意位置 | 只能栈顶 |
| 删除位置 | 任意位置 | 只能栈顶 |
| 访问方式 | 随机访问（下标/迭代器） | 只能访问栈顶 |
二、stack的“基本招式”
1. 创建stack
#include <stack>
using namespace std;stack<int> s1; // 默认基于deque的栈
stack<string, vector<string>> s2; // 基于vector的栈
stack<char> s3({ 'a', 'b' }); // 初始化栈（C++11起）
2. 入栈与出栈
s1.push(10); // 栈顶添加元素：10 → 20 → 30
s1.push(20);
s1.push(30);s1.pop(); // 移除栈顶元素（30被移除）
// 注意：pop()不返回栈顶值！需先通过top()获取
3. 访问栈顶
cout << s1.top(); // 输出20（当前栈顶元素）
// s1.top() = 100; // 可以修改栈顶元素
4. 查看信息
if (s1.empty()) { /* 栈是否为空 */ }
cout << s1.size(); // 栈中元素个数
三、stack的“实现原理”
std::stack是一个容器适配器，默认使用deque作为底层容器，但也可指定其他容器（需支持back()、push_back()、pop_back()操作）：
// 基于vector实现栈
stack<int, vector<int>> vecStack;
// 基于list实现栈
stack<string, list<string>> listStack;
为什么选择deque作为默认容器？
- 动态扩容：
deque支持高效的前后插入/删除，内存分配比vector更均衡。 - 避免拷贝：扩容时不需要整体迁移数据。
四、stack的“实战场景”
1. 函数调用栈
程序执行函数时，系统栈用于保存函数返回地址、局部变量等：
void funcA() { funcB(); } // funcA入栈 → funcB入栈 → funcB出栈 → funcA出栈
void funcB() { /* ... */ }
2. 括号匹配检查
bool isBalanced(string expr) {stack<char> s;for (char c : expr) {if (c == '(' || c == '[') s.push(c);else if (c == ')') {if (s.empty() || s.top() != '(') return false;s.pop();} else if (c == ']') {if (s.empty() || s.top() != '[') return false;s.pop();}}return s.empty();
}
// 示例：isBalanced("([()])") → true
3. 撤销操作（Undo）
文本编辑器中的撤销功能通常用栈实现：
stack<string> history;
history.push("Hello"); // 当前文本："Hello"
history.push("Hello World"); // 编辑后入栈
history.pop(); // 撤销到上一步："Hello"
4. 深度优先搜索（DFS）
图或树的DFS算法依赖栈结构：
stack<Node*> dfsStack;
dfsStack.push(rootNode);
while (!dfsStack.empty()) {Node* current = dfsStack.top();dfsStack.pop();// 处理当前节点，并将其子节点入栈
}
五、stack的“使用禁忌”
1. 禁止随机访问
// 错误示例：尝试访问中间元素
// cout << s1[1]; // 编译错误！stack没有[]运算符
2. 空栈操作
stack<int> s;
// cout << s.top(); // 未定义行为（崩溃！）
// s.pop(); // 同样危险！
3. 误用递归导致栈溢出
虽然与数据结构栈不同，但递归深度过大会导致系统调用栈溢出：
void infiniteRecursion() {infiniteRecursion(); // 最终引发栈溢出错误（Stack Overflow）
}
六、stack的“性能秘籍”
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
push() | O(1) | 添加元素到栈顶 |
pop() | O(1) | 移除栈顶元素 |
top() | O(1) | 访问栈顶元素 |
size() | O(1) | 返回元素数量 |
最佳实践：
- 优先使用默认的
deque作为底层容器。 - 避免在栈中存储过大对象（可能影响缓存性能）。
七、动手实验
1. 反转字符串
string reverseString(const string& str) {stack<char> s;for (char c : str) s.push(c);string reversed;while (!s.empty()) {reversed += s.top();s.pop();}return reversed;
}
// reverseString("hello") → "olleh"
2. 模拟浏览器历史记录
stack<string> backHistory, forwardHistory;
string currentPage = "home";void visitPage(const string& url) {backHistory.push(currentPage);currentPage = url;while (!forwardHistory.empty()) forwardHistory.pop();
}void goBack() {if (!backHistory.empty()) {forwardHistory.push(currentPage);currentPage = backHistory.top();backHistory.pop();}
}
总结：stack——简单而强大的“规则执行者”
std::stack以其简洁的接口和高效的LIFO管理，成为处理特定问题的理想工具。
- 像厨师叠盘子：严格遵守“后进先出”的规则，确保操作有序。
- 像魔法师操控时间：用撤销操作和函数调用栈“逆转时空”。
下次当你需要处理“反向依赖”或“步骤回溯”的问题时，不妨让stack成为你的得力助手——它不仅是容器，更是逻辑控制的隐形推手！
（完）
希望这篇博客能让读者轻松掌握C++ stack的核心技巧！如果需要调整示例或补充细节，请随时告诉我~ 😊