Stack
487 字
2 分钟
Stack
核心概念
- 本质：容器适配器，后进先出（LIFO）数据结构
- 头文件：
#include <stack> - 命名空间：
std:: - 底层容器：默认使用
deque，也可指定vector或list - 特点：只允许在栈顶进行插入和删除操作
- 复杂度：所有操作的时间复杂度都是 O(1)
构造函数
| 接口 | 说明 |
|---|---|
stack<T> st; | 默认构造，创建空stack |
stack<T> st(other_stack); | 拷贝构造 |
stack<T> st(container); | 使用指定底层容器构造 |
stack<T> st = other_stack; | 拷贝赋值 |
指定底层容器示例：
stack<int> st1; // 默认使用dequestack<int, vector<int>> st2; // 使用vector作为底层容器stack<int, list<int>> st3; // 使用list作为底层容器容量操作
接口 | 说明 |
|---|---|
st.empty() | 检查stack是否为空 |
st.size() | 返回元素数量 |
元素访问
接口 | 说明 |
|---|---|
st.top() | 返回栈顶元素的引用 |
修改器
接口 | 说明 |
|---|---|
st.push(value) | 将元素压入栈顶 |
st.pop() | 弹出栈顶元素 |
st.emplace(args...) | 在栈顶就地构造元素 |
st.swap(other_stack) | 交换两个stack的内容 |
非成员函数
接口 | 说明 |
|---|---|
swap(st1,st2) | 交换两个stack的内容 |
operator== | 相等比较 |
operator！= | 不等比较 |
operator< | 小于比较 |
operator<= | 小于等于比较 |
注意事项
- 访问前检查：调用 top() 或 pop() 前必须确保栈不为空
- pop()不返回值：pop() 只移除元素，不返回元素值，需要先使用 top() 获取
- 底层容器限制：选择的底层容器必须支持 back(), push_back(), pop_back() 操作
- 迭代器：stack 不提供迭代器，无法直接遍历
- 异常安全：pop() 通常不抛出异常，但 top() 和 push() 可能抛出
- 性能考虑： · 默认 deque：平衡了头尾操作性能 · vector：可能涉及更多内存重新分配 · list：每个操作都是常数时间，但内存开销大
常见应用场景
· 函数调用栈 · 表达式求值 · 括号匹配 · 深度优先搜索（DFS） · 撤销/重做功能 · 浏览器历史记录
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
相关文章智能推荐
1
Queue
STL本质：容器适配器，先进先出（FIFO）数据结构 头文件：include 命名空间：std:: 底层容器：默认使用 deque，也可指定 list 特点：只允许在队尾插入，队头删除 复杂度：所有操作的时间复杂度都是 O(1)
2
Deque
STL本质：双端队列，序列容器 头文件：include 命名空间：std:: 特点：支持在头部和尾部高效插入删除，支持随机访问 复杂度：头尾插入删除 O(1)，随机访问 O(1)，中间插入删除 O(n) 内存结构：由多个固定大小的块组成，不是完…
3
List
STL本质：双向链表容器 头文件：include 命名空间：std:: 优点：任意位置插入删除高效 O(1)，不需要连续内存 缺点：不支持随机访问，访问元素需要遍历 O(n)，内存开销较大（每个节点包含前后指针） 特点：双向迭代器，插入删除不会…
4
vector
STL本质：动态数组，大小可变 内存：连续存储空间 头文件：include 命名空间：std:: 优点：随机访问快，尾部操作高效，自动内存管理 缺点：中间插入/删除慢，内存占用可能较高
5
String
STL本质：动态字符序列，封装了字符串操作 头文件：include 命名空间：std:: 优点：自动内存管理，丰富的字符串操作，支持C风格字符串转换 底层：通常包含长度信息，不以\0作为必需结尾（但支持C风格转换）
随机文章随机推荐