csp信奥赛C++标准模板库STL（8）：stack的使用详解
一、什么是栈？
栈是一种后进先出（LIFO，Last In First Out）的数据结构，类似于现实生活中的一叠盘子或书籍。
二、栈的基本特性
- 只能在栈顶进行插入和删除操作
- 插入操作：称为入栈（push）
- 删除操作：称为出栈（pop）
- 访问操作：只能访问栈顶（top）元素
三、C++ STL 中的 stack
定义和初始化
#include<stack>// 基本定义stack<int>s1;// 默认使用deque作为底层容器// 初始化为另一个栈的副本stack<int>s2(s1);四、stack 的主要成员函数
| 方法 | 功能 | 时间复杂度 |
|---|---|---|
push(x) | 将元素x压入栈顶 | O(1) |
pop() | 弹出栈顶元素 | O(1) |
top() | 返回栈顶元素 | O(1) |
empty() | 判断栈是否为空 | O(1) |
size() | 返回栈中元素个数 | O(1) |
五、基本操作示例
#include<iostream>#include<stack>usingnamespacestd;intmain(){stack<int>s;// 入栈操作s.push(10);s.push(20);s.push(30);// 查看栈顶元素cout<<"栈顶元素: "<<s.top()<<endl;// 输出: 30// 查看栈的大小cout<<"栈的大小: "<<s.size()<<endl;// 输出: 3// 出栈操作s.pop();cout<<"出栈后栈顶元素: "<<s.top()<<endl;// 输出: 20// 判断栈是否为空if(!s.empty()){cout<<"栈不为空"<<endl;}// 遍历栈（注意：遍历会清空栈）cout<<"栈中元素（从栈顶到栈底）: ";while(!s.empty()){cout<<s.top()<<" ";s.pop();}// 输出: 20 10cout<<endl;return0;}六、信奥赛中栈的常见应用
案例1. 括号匹配问题
boolisValid(string s){stack<char>st;for(charc:s){if(c=='('||c=='['||c=='{'){st.push(c);}else{if(st.empty())returnfalse;chartop=st.top();if((c==')'&&top!='(')||(c==']'&&top!='[')||(c=='}'&&top!='{')){returnfalse;}st.pop();}}returnst.empty();}案例2. 表达式求值（后缀表达式）
intfun(vector<string>&tokens){stack<int>st;for(string&token:tokens){if(token=="+"||token=="-"||token=="*"||token=="/"){intb=st.top();st.pop();inta=st.top();st.pop();if(token=="+")st.push(a+b);elseif(token=="-")st.push(a-b);elseif(token=="*")st.push(a*b);elsest.push(a/b);}else{st.push(stoi(token));}}returnst.top();}七、注意事项
访问前检查空栈：调用
top()或pop()前务必使用empty()检查if(!st.empty()){intval=st.top();st.pop();}栈不能直接遍历：需要遍历时，可以复制一份或使用临时栈
voidprintStack(stack<int>s){// 值传递，不修改原栈while(!s.empty()){cout<<s.top()<<" ";s.pop();}}性能考虑：stack的底层默认使用deque，也可以使用vector或list，但各有优劣：
deque（默认）：两端插入删除高效vector：内存连续，但扩大时需要重新分配list：不需要连续内存，但内存开销较大
总结
栈在信息学奥赛中是非常重要的数据结构，常用于：
- 括号匹配、表达式求值
- 深度优先搜索的非递归实现
- 单调栈解决"下一个更大/小元素"问题
- 撤销操作、函数调用等场景
掌握栈的应用是提高算法能力的关键一步，建议多练习相关的题目来加深理解。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
