113 std::stack
作者Lou Xiao, deepseek创建时间2025-04-02 17:44:58更新时间2025-04-02 17:44:58
1. 概述
std::stack 是 C++ 标准模板库(STL)中的一个容器适配器，它提供了栈(后进先出，LIFO)数据结构的功能。
2. 基本特性
- 容器适配器：基于其他容器实现(默认使用
std::deque) - LIFO原则：Last In First Out (后进先出)
- 头文件：
#include <stack> - 命名空间：
std
3. 模板声明
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
template <class T, class Container = deque<T>>
2
class stack;
T: 存储的元素类型Container: 底层容器类型(默认为std::deque)
4. 支持的底层容器
std::deque(默认)std::vectorstd::list
5. 成员函数
5.1 元素访问
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
top() | 返回栈顶元素的引用 | O(1) |
5.2 容量操作
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
empty() | 检查栈是否为空 | O(1) |
size() | 返回栈中元素数量 | O(1) |
5.3 修改操作
| 函数 | 描述 | 时间复杂度 |
|---|---|---|
push(const T& value) | 将元素压入栈顶 | O(1) |
push(T&& value) | 移动元素到栈顶(C++11) | O(1) |
emplace(args...) | 在栈顶原位构造元素(C++11) | O(1) |
pop() | 移除栈顶元素 | O(1) |
swap(stack& other) | 交换两个栈的内容(C++11) | O(1) |
6. 非成员函数
| 函数 | 描述 |
|---|---|
operator== | 比较两个栈是否相等 |
operator!= | 比较两个栈是否不相等 |
operator< | 按字典序比较 |
operator<= | 按字典序比较 |
operator> | 按字典序比较 |
operator>= | 按字典序比较 |
swap(stack& a, stack& b) | 交换两个栈的内容 |
7. 使用示例
7.1 基本使用
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <iostream>
2
#include <stack>
3
4
int main() {
5
std::stack<int> s;
6
7
// 压入元素
8
s.push(1);
9
s.push(2);
10
s.push(3);
11
12
// 访问栈顶元素
13
std::cout << "Top element: " << s.top() << std::endl; // 输出 3
14
15
// 弹出元素
16
s.pop();
17
std::cout << "After pop, top element: " << s.top() << std::endl; // 输出 2
18
19
// 检查大小
20
std::cout << "Stack size: " << s.size() << std::endl; // 输出 2
21
22
// 检查是否为空
23
std::cout << "Is empty: " << std::boolalpha << s.empty() << std::endl; // 输出 false
24
}
7.2 使用不同底层容器
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <stack>
2
#include <vector>
3
#include <list>
4
5
int main() {
6
// 使用vector作为底层容器
7
std::stack<int, std::vector<int>> stack_vec;
8
9
// 使用list作为底层容器
10
std::stack<int, std::list<int>> stack_list;
11
}
7.3 emplace使用(C++11)
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <stack>
2
#include <string>
3
4
int main() {
5
std::stack<std::string> s;
6
7
// 使用emplace直接在栈顶构造元素
8
s.emplace("Hello");
9
s.emplace("World");
10
11
std::cout << s.top() << std::endl; // 输出 "World"
12
}
8. 注意事项
- 异常安全：
push()和emplace()在底层容器空间不足时可能抛出异常 - 空栈访问：调用
top()或pop()前必须确保栈不为空，否则是未定义行为 - 性能考虑：
- 对于频繁的push/pop操作，
std::deque(默认)通常是最佳选择 - 如果需要连续内存，可以选择
std::vector，但要注意扩容时的性能影响
- 对于频繁的push/pop操作，
- 线程安全：
std::stack本身不是线程安全的，多线程环境下需要额外同步
9. 典型应用场景
- 函数调用栈
- 表达式求值
- 括号匹配检查
- 深度优先搜索(DFS)
- 撤销(Undo)操作实现
10. 与其它容器的比较
| 特性 | std::stack | std::vector | std::deque | std::list |
|---|---|---|---|---|
| 访问方式 | 仅栈顶 | 随机访问 | 随机访问 | 顺序访问 |
| 插入/删除位置 | 仅栈顶 | 任意位置 | 两端高效 | 任意位置 |
| 内存布局 | 依赖底层容器 | 连续 | 分块连续 | 非连续 |
| 迭代器支持 | 无 | 有 | 有 | 有 |
11. 扩展知识
- 自定义栈实现：可以通过继承或组合方式基于其他容器实现自定义栈
- 线程安全栈：可以通过封装
std::stack并添加互斥锁实现线程安全版本 - 栈的变体：
- 最小栈(能在O(1)时间内获取当前栈中最小元素)
- 双栈(在一个数组中实现两个栈)
std::stack 常用 API 的整理表格
| 名称 | 用途 | 原型 | 代码示例 | 注释 |
|---|---|---|---|---|
| push | 将元素压入栈顶 | void push(const T& value);void push(T&& value); | std::stack<int> s;s.push(10); | 通过拷贝或移动将元素添加到栈顶。 |
| emplace | 在栈顶直接构造元素 | template<class... Args>void emplace(Args&&... args); | std::stack<std::pair<int, int>> s;s.emplace(1, 2); | 避免拷贝/移动，直接在栈顶构造元素（C++11 引入）。 |
| pop | 移除栈顶元素 | void pop(); | std::stack<int> s;s.push(10);s.pop(); | 不返回被移除的元素，需先通过 top() 获取。 |
| top | 访问栈顶元素 | T& top();const T& top() const; | std::stack<int> s;s.push(10);int x = s.top(); | 返回栈顶元素的引用（可修改非 const 版本）。 |
| size | 返回栈中元素数量 | size_type size() const; | std::stack<int> s;s.push(10);size_t count = s.size(); | 返回值为 size_type（通常为 size_t）。 |
| empty | 检查栈是否为空 | bool empty() const; | if (s.empty()) { /* ... */ } | 等价于 size() == 0，但可能更高效。 |
| swap | 交换两个栈的内容 | void swap(stack& other) noexcept; | std::stack<int> s1, s2;s1.swap(s2); | 高效交换底层容器（C++11 引入，支持 noexcept）。 |
补充说明
- 底层容器：
std::stack默认基于std::deque，也可指定其他容器（如std::vector或std::list）：std::stack<int, std::vector<int>> v_stack; - 非成员函数：
std::swap(stack1, stack2)可交换两个栈（与成员函数swap等效）。 - 错误处理：调用
top()或pop()前需确保栈非空，否则行为未定义（UB）。
示例代码（综合）
1.双击鼠标左键复制此行；2.单击复制所有代码。
1
#include <stack>
2
#include <iostream>
3
4
int main() {
5
std::stack<int> s;
6
s.push(1); // 栈: [1]
7
s.emplace(2); // 栈: [1, 2]
8
std::cout << s.top(); // 输出 2
9
s.pop(); // 栈: [1]
10
if (!s.empty()) {
11
std::cout << s.size(); // 输出 1
12
}
13
return 0;
14
}
文章目录