异常教程
C++ 容器类 <stack>（保姆级教程）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论
- 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于
Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;- 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;
截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观
在 C++ 的标准模板库（STL）中，容器类 <stack> 是一种非常实用的数据结构，它通过严格的 后进先出（LIFO, Last-In-First-Out） 原则管理数据。无论是实现算法中的递归替代方案、处理括号匹配问题，还是构建表达式求值器，<stack> 都能提供简洁高效的解决方案。对于编程初学者而言，理解 <stack> 的核心概念和用法，能够显著提升代码逻辑的清晰度；而对中级开发者来说，深入其底层实现原理和高级特性，则有助于优化复杂场景下的性能表现。本文将从基础概念到实战案例，系统性地解析这一容器类的奥秘。
一、栈（Stack）的基本概念与特性
1.1 栈的定义与比喻
栈是一种只能在一端进行插入和删除操作的线性数据结构。想象一个托盘叠放的场景：每次新物品必须放在最顶端，取出时也只能从顶端拿走，这就是典型的 LIFO 模型。在 C++ 中，<stack> 容器类通过 push()（压入）、pop()（弹出）、top()（获取顶端元素）等操作，严格遵循这一规则。
1.2 栈的五大核心操作
| 操作 | 功能描述 | 时间复杂度 |
|---|---|---|
push(value) | 将元素添加到栈顶 | O(1) |
pop() | 移除栈顶元素（不返回值） | O(1) |
top() | 访问栈顶元素（不移除） | O(1) |
empty() | 检查栈是否为空 | O(1) |
size() | 返回栈中元素数量 | O(1) |
1.3 栈的典型应用场景
- 括号匹配：检查表达式中的括号是否成对出现。
- 函数调用栈：操作系统通过栈管理函数调用的返回地址。
- Undo/Redo 功能：通过两个栈分别记录操作的撤销与重做步骤。
二、C++ 中 <stack> 的实现原理与容器适配器
2.1 容器适配器的定位
<stack> 并非独立的底层容器，而是 C++ STL 提供的容器适配器（Container Adapters）。它通过封装其他容器（如 vector、deque 或 list），限制其操作接口以实现栈的特性。例如，默认情况下，stack 使用 deque 作为底层容器，但开发者可以通过模板参数自定义。
2.2 底层容器的选择与性能对比
#include <stack>
#include <vector>
// 默认使用 deque 作为底层容器
std::stack<int> default_stack;
// 显式指定 vector 作为底层容器
std::stack<int, std::vector<int>> vector_based_stack;
deque的优势：支持高效的push()和pop()，且top()操作直接访问首元素。vector的适用场景：当需要频繁访问栈底元素时，可通过vector的随机访问特性优化性能。
2.3 栈的不可变性约束
由于栈仅允许一端操作，其底层容器的某些功能被禁止。例如：
std::stack<int> s;
// 错误：无法通过迭代器或索引访问中间元素
// s[2] = 10; // 编译报错
这种设计确保了数据结构的封装性，避免意外破坏 LIFO 规则。
三、实战案例：用 <stack> 解决经典问题
3.1 括号匹配问题
问题描述：判断字符串中的括号是否合法，如 "({[]})" 是合法的，而 "([)]" 是非法的。
解决方案：
#include <stack>
#include <string>
bool is_valid(const std::string& s) {
std::stack<char> bracket_stack;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
bracket_stack.push(c);
} else {
if (bracket_stack.empty()) return false;
char top = bracket_stack.top();
bracket_stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return bracket_stack.empty();
}
关键点：栈的 LIFO 特性完美匹配括号的嵌套关系，确保每个右括号都能与最近的左括号配对。
3.2 后缀表达式求值
问题描述：将中缀表达式（如 3 + 4 * 2）转换为后缀表达式（如 3 4 2 * +），并计算结果。
核心代码片段：
#include <stack>
int evaluate_postfix(const std::string& expr) {
std::stack<int> operand_stack;
for (char c : expr) {
if (isdigit(c)) {
operand_stack.push(c - '0');
} else {
int b = operand_stack.top(); operand_stack.pop();
int a = operand_stack.top(); operand_stack.pop();
switch (c) {
case '+': operand_stack.push(a + b); break;
case '-': operand_stack.push(a - b); break;
// 其他运算符类似
}
}
}
return operand_stack.top();
}
原理：栈用于临时存储操作数，确保运算顺序与后缀表达式一致，避免优先级冲突。
四、高级特性与常见陷阱
4.1 自定义容器类型
开发者可通过模板参数指定底层容器类型，甚至自定义容器：
struct MyContainer : std::deque<int> {
// 可添加自定义方法
};
std::stack<int, MyContainer> custom_stack;
注意：底层容器必须支持 push_back()、pop_back()、back() 等接口，否则编译会报错。
4.2 空栈操作的异常处理
直接对空栈调用 top() 或 pop() 会导致未定义行为（Undefined Behavior）。建议通过 empty() 检查后再操作：
if (!s.empty()) {
int top_value = s.top();
// ...
}
4.3 线程安全问题
C++ 标准库的 <stack> 并非线程安全。在多线程环境中，需自行通过 std::mutex 等机制加锁：
std::stack<int> shared_stack;
std::mutex mtx;
void push_safe(int value) {
std::lock_guard<std::mutex> lock(mtx);
shared_stack.push(value);
}
五、常见问题解答
Q1：为什么 stack 要基于其他容器实现？
A：容器适配器的设计体现了面向接口编程的思想。通过限制操作接口，确保数据结构符合特定规则（如 LIFO），同时复用已有容器的高效实现。
Q2：如何选择底层容器类型？
A：
- 若需频繁弹出栈底元素，选择
list（通过pop_front()）； - 若仅需顶端操作，
deque或vector的性能差异可忽略。
Q3：stack 与 queue 的区别？
A：
stack遵循 LIFO，queue遵循 FIFO（先进先出）；queue的front()和back()操作对应队列的两端，而stack仅操作一端。
C++ 容器类 <stack> 是解决特定问题的高效工具，其简洁的接口和严格的 LIFO 约束，使其在算法设计中扮演重要角色。无论是处理括号匹配、表达式求值，还是实现回溯算法，开发者都能通过 <stack> 快速构建逻辑清晰的解决方案。然而，理解其底层实现原理和潜在陷阱（如空栈操作、线程安全）同样关键，这将帮助开发者避免低级错误，并写出更健壮的代码。
掌握 <stack> 的核心用法后，建议进一步探索其他容器适配器（如 <queue>、<priority_queue>），以及结合 STL 算法（如 std::for_each）实现更复杂的逻辑。通过持续实践，开发者将能充分挖掘 C++ 标准库的强大功能，提升编码效率与代码质量。