栈
2026-05-07 21:10:58
发布于：浙江
8阅读
0回复
0点赞
C++ stack
1 为什么需要栈
1.1 现实抽象
- 浏览器后退
- 函数调用
- 表达式求值
- 撤销操作（Undo）
1.2 抽象模型
栈是受限线性表：
只允许在一端操作。
2 STL stack 本质
2.1 容器适配器（Adapter）
template<
typename T,
typename Container=deque<T>
>class stack;
✅ 不自己存数据
✅ 复用底层容器接口
2.2 默认底层
| 底层容器 | 是否允许 |
|---|---|
deque |
✅ 默认 |
vector |
✅ |
list |
✅ |
array |
❌ |
3 定义方式
stack<int>s;
stack<int,vector<int>>s;
stack<double,list<double>>s;
4 核心操作
| 语义 | 函数 | 复杂度 |
|---|---|---|
| 入栈 | push(x) |
|
| 出栈 | pop() |
|
| 取顶 | top() |
|
| 判空 | empty() |
|
| 大小 | size() |
5 基础示例
#include<iostream>
#include<stack>
using namespace std;
int main(){
stack<int>s;
s.push(1);
s.push(2);
s.push(3);
cout<<s.top()<<endl;
s.pop();
cout<<s.top()<<endl;
return 0;
}
6 栈的数学性质
6.1 出栈序列数（卡特兰数）
入栈序列：
合法出栈序列数为：
6.2 递归与栈等价性
任意递归：
等价于显式栈模拟。
7 经典算法应用
7.1 括号匹配
bool f(string t){
stack<char>s;
for(char c:t){
if(c=='('||c=='{'||c=='['){
s.push(c);
}else{
if(s.empty())return false;
char x=s.top();
if((c==')'&&x!='(')||
(c=='}'&&x!='{')||
(c==']'&&x!='[')){
return false;
}
s.pop();
}
}
return s.empty();
}
7.2 单调栈（Monotonic Stack）
问题抽象
对每个元素，找：
算法思想
维护单调递减栈：
模板代码
vector<int>f(vector<int>&a){
int n=a.size();
vector<int>r(n,-1);
stack<int>s;
for(int i=0;i<n;i++){
while(!s.empty()&&a[s.top()]<a[i]){
r[s.top()]=a[i];
s.pop();
}
s.push(i);
}
return r;
}
7.3 表达式求值（后缀）
中缀转后缀
优先级：
计算核心
int calc(string t){
stack<int>s;
int x=0;
for(char c:t){
if(isdigit(c)){
x=x*10+(c-'0');
}else{
int b=s.top();s.pop();
int a=s.top();s.pop();
if(c=='+')x=a+b;
if(c=='-')x=a-b;
if(c=='*')x=a*b;
if(c=='/')x=a/b;
s.push(x);
x=0;
}
}
return s.top();
}
8 手写栈（理解 STL 本质）
struct Stack{
int a[10005],t;
void push(int x){a[++t]=x;}
void pop(){t--;}
int top(){return a[t];}
bool empty(){return t==0;}
}s;
9 性能与工程注意
9.1 复杂度总结
| 操作 | 平均 | 最坏 |
|---|---|---|
| push/pop | O(1) | O(1) |
9.2 常见坑
top()前未判空pop()不返回值- 递归过深 → 栈溢出
vector底层可能扩容
10 进阶方向
- ✅ 双栈队列
- ✅ 最小栈（Min Stack）
- ✅ 栈帧 & 调用约定
- ✅ 编译器语法分析
- ✅ JVM / OS 调用栈
有帮助，赞一个