c++ stack用法详解
C++ std::stack
用法详解(2025 版,超详细)
std::stack
是 C++ 标准模板库(STL)提供的一种栈数据结构,遵循后进先出(LIFO, Last In First Out)原则,位于 <stack>
头文件。它基于适配器模式,默认底层容器为 std::deque
,也可指定 std::vector
或 std::list
。本教程从基础概念到高级应用,详细讲解 std::stack
的用法、原理和场景,结合代码示例,适合初学者到进阶开发者。内容基于 C++20 标准(截至 2025 年 10 月),参考 CPPReference 和社区资源(如 CSDN、GeeksforGeeks)。
第一阶段:std::stack
基础概念(初学者级别)
1.1 什么是 std::stack
?
- 定义:
std::stack
是 STL 提供的容器适配器,封装了底层容器(如deque
),提供栈操作接口:入栈(push
)、出栈(pop
)、访问栈顶(top
)等。 - 核心特性:
- LIFO:最后入栈的元素最先出栈。
- 限制访问:只能操作栈顶,无法直接访问中间元素。
- 无迭代器:不像
std::vector
支持随机访问,栈只提供栈顶操作。 - 头文件:
#include <stack>
- 类模板:
template <class T, class Container = std::deque<T>>
class stack;
T
:存储元素类型(如int
、std::string
)。Container
:底层容器(默认std::deque
,支持std::vector
、std::list
)。
类比:std::stack
像一叠盘子,只能从顶部放或取。
1.2 核心操作
函数 | 功能 | 时间复杂度 |
---|---|---|
push(value) | 入栈(添加元素到栈顶) | O(1)(均摊) |
pop() | 出栈(移除栈顶元素,无返回值) | O(1) |
top() | 访问栈顶元素 | O(1) |
empty() | 检查栈是否为空 | O(1) |
size() | 返回元素个数 | O(1) |
swap(other) | 交换两个栈内容 | O(1)(依赖底层容器) |
注意:
pop()
不返回栈顶值,需先用top()
获取。- 访问空栈的
top()
或pop()
导致未定义行为,需先检查empty()
。
1.3 基本示例
#include <iostream>
#include <stack>
int main() {
std::stack<int> s;
s.push(1); // 入栈 1
s.push(2); // 入栈 2
s.push(3); // 入栈 3
std::cout << "Top: " << s.top() << std::endl; // 输出栈顶
s.pop(); // 移除 3
std::cout << "Top after pop: " << s.top() << std::endl;
std::cout << "Size: " << s.size() << std::endl;
std::cout << "Empty: " << (s.empty() ? "Yes" : "No") << std::endl;
return 0;
}
输出:
Top: 3
Top after pop: 2
Size: 2
Empty: No
第二阶段:std::stack
原理与实现(中级)
2.1 底层容器
std::stack
是容器适配器,依赖底层容器实现操作。- 默认容器:
std::deque
(双端队列,高效尾部操作)。 - 可选容器:
std::vector
:适合动态扩展,但尾部插入稍慢。std::list
:适合频繁插入/删除,但无随机访问。- 自定义容器:需满足 STL 容器要求(
back()
、push_back()
、pop_back()
)。 - 示例(指定容器):
#include <stack>
#include <vector>
std::stack<int, std::vector<int>> s; // 使用 vector 作为底层容器
2.2 实现原理
- 适配器模式:
std::stack
封装底层容器,仅暴露栈接口。 - 源码简化(参考 C++20):
template <class T, class Container = std::deque<T>>
class stack {
protected:
Container c; // 底层容器
public:
void push(const T& value) { c.push_back(value); }
void pop() { c.pop_back(); }
T& top() { return c.back(); }
bool empty() const { return c.empty(); }
size_t size() const { return c.size(); }
};
- 性能:
- 依赖底层容器:
deque
和vector
的尾部操作是 O(1)。 - 空间复杂度:O(n),n 为元素个数。
2.3 异常安全
- push:若底层容器分配失败,可能抛出
std::bad_alloc
。 - pop/top:不抛异常,但空栈操作导致未定义行为。
- 最佳实践:操作前检查
!s.empty()
。
第三阶段:高级用法与优化(高级)
3.1 自定义类型栈
- 要求:类型需支持拷贝或移动构造。
- 示例(自定义类):
#include <iostream>
#include <stack>
#include <string>
struct Student {
std::string name;
int id;
Student(std::string n, int i) : name(n), id(i) {}
friend std::ostream& operator<<(std::ostream& os, const Student& s) {
return os << s.name << ": " << s.id;
}
};
int main() {
std::stack<Student> s;
s.push({"Alice", 1});
s.push({"Bob", 2});
std::cout << "Top: " << s.top() << std::endl;
s.pop();
std::cout << "Top after pop: " << s.top() << std::endl;
return 0;
}
输出:
Top: Bob: 2
Top after pop: Alice: 1
3.2 自定义容器
- 示例(用
std::list
):
#include <stack>
#include <list>
std::stack<int, std::list<int>> s; // 使用 list
s.push(1); // 底层调用 list::push_back
3.3 性能优化
- 选择容器:
std::deque
(默认):适合大多数场景,尾部操作高效。std::vector
:若需要连续内存(缓存友好),但扩容可能导致拷贝。std::list
:若频繁插入/删除,但内存开销稍大。- 预分配(间接):
std::stack
无reserve
,但可通过自定义容器预分配:cpp std::vector<int> vec; vec.reserve(1000); // 预分配 std::stack<int, std::vector<int>> s(std::move(vec));
- 避免空栈操作:
if (!s.empty()) {
s.pop();
}
3.4 比较与交换
- 比较:支持
==
、!=
等(比较底层容器)。 - 交换:
s1.swap(s2)
,高效交换底层容器。
std::stack<int> s1, s2;
s1.swap(s2); // O(1)
第四阶段:实际应用场景 + 举例
4.1 场景 1:表达式求值(后缀表达式)
栈常用于解析表达式(如 3 + 4 * 2
转为后缀 3 4 2 * +
)。
#include <iostream>
#include <stack>
#include <string>
int evaluate_postfix(const std::string& expr) {
std::stack<int> s;
for (char c : expr) {
if (isdigit(c)) {
s.push(c - '0');
} else {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
if (c == '+') s.push(a + b);
else if (c == '*') s.push(a * b);
}
}
return s.top();
}
int main() {
std::string expr = "342*+"; // (3 + 4 * 2)
std::cout << "Result: " << evaluate_postfix(expr) << std::endl;
return 0;
}
输出:Result: 11
4.2 场景 2:括号匹配
检查括号是否匹配(如 ({[]})
)。
#include <iostream>
#include <stack>
#include <string>
bool is_valid_parentheses(const std::string& s) {
std::stack<char> stack;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
stack.push(c);
} else {
if (stack.empty()) return false;
char top = stack.top(); stack.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return stack.empty();
}
int main() {
std::string expr = "{[()]}";
std::cout << "Valid: " << (is_valid_parentheses(expr) ? "Yes" : "No") << std::endl;
return 0;
}
输出:Valid: Yes
4.3 场景 3:任务撤销(Undo)
栈记录操作历史,支持撤销。
#include <iostream>
#include <stack>
#include <string>
int main() {
std::stack<std::string> undo_stack;
undo_stack.push("Edit 1");
undo_stack.push("Edit 2");
std::cout << "Undo: " << undo_stack.top() << std::endl; // Edit 2
undo_stack.pop();
std::cout << "Undo: " << undo_stack.top() << std::endl; // Edit 1
return 0;
}
输出:
Undo: Edit 2
Undo: Edit 1
第五阶段:常见问题与最佳实践
5.1 常见问题
问题 | 原因 | 解决方案 |
---|---|---|
未定义行为 | 空栈调用 top() 或 pop() | 检查 !s.empty() 。 |
性能瓶颈 | 底层容器扩容 | 用 std::vector 预分配(reserve )。 |
头文件缺失 | 未包含 <stack> | 添加 #include <stack> 。 |
自定义类型失败 | 无拷贝/移动构造 | 实现构造/赋值运算符。 |
5.2 最佳实践
- 检查空栈:操作前用
s.empty()
。 - 选择容器:默认
std::deque
适合大多数场景。 - 异常安全:捕获
push
的std::bad_alloc
。 - 调试:打印栈内容(需临时 pop 并 push)。
while (!s.empty()) {
std::cout << s.top() << " "; s.pop();
}
- 替代:若需先进先出,考虑
std::queue
。
5.3 性能测试
#include <iostream>
#include <stack>
#include <chrono>
int main() {
std::stack<int> s;
auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 1000000; i++) {
s.push(i);
}
while (!s.empty()) {
s.pop();
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Time: "
<< std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
<< " us" << std::endl;
return 0;
}
输出(示例,i7-12700):Time: ~5000 us
(100 万次 push/pop)。
第六阶段:资源与进阶学习
- 学习路径:
- 1 天:掌握基本操作(push/pop/top)。
- 2-3 天:实践场景(表达式、括号匹配)。
- 1 周:自定义类型、容器优化。
- 资源:
- 官方:CPPReference (
std::stack
, https://en.cppreference.com/w/cpp/container/stack). - 英文:GeeksforGeeks (https://www.geeksforgeeks.org/stack-in-cpp-stl/).
- 中文:CSDN (https://blog.csdn.net/weixin_43883374/article/details/106926058) – STL 容器。
- 书籍:《C++ Primer》(Lippman),第 9 章。
- 视频:YouTube “C++ STL Stack” by The Cherno。
- 工具:GCC 14+、Clang 17+、MSVC 2022、VS Code。
总结:std::stack
是高效的 LIFO 数据结构,基于 std::deque
,提供简单接口。适合表达式求值、撤销操作等场景。优先使用 STL 实现,注意空栈检查和容器选择。若有具体问题(如性能优化),欢迎提供代码,我可进一步指导!
include
include
include
bool is_valid_parentheses(const std::string& s) {
std::stack stack;
for (char c : s) {
if (c == ‘(‘ || c == ‘{‘ || c == ‘[‘) {
stack.push(c);
} else {
if (stack.empty()) return false;
char top = stack.top(); stack.pop();
if ((c == ‘)’ && top != ‘(‘) ||
(c == ‘}’ && top != ‘{‘) ||
(c == ‘]’ && top != ‘[‘)) {
return false;
}
}
}
return stack.empty();
}
int main() {
std::string expr = “{[()]}”;
std::cout << “Valid: ” << (is_valid_parentheses(expr) ? “Yes” : “No”) << std::endl; return 0; }