csp信奥赛C++标准模板库STL（8）：stack的使用详解

csp信奥赛C++标准模板库STL（8）：stack的使用详解

一、什么是栈？

栈是一种后进先出（LIFO，Last In First Out）的数据结构，类似于现实生活中的一叠盘子或书籍。

二、栈的基本特性

1. 只能在栈顶进行插入和删除操作
2. 插入操作：称为入栈（push）
3. 删除操作：称为出栈（pop）
4. 访问操作：只能访问栈顶（top）元素

三、C++ STL 中的 stack

定义和初始化

#include<stack>// 基本定义stack<int>s1;// 默认使用deque作为底层容器// 初始化为另一个栈的副本stack<int>s2(s1);

四、stack 的主要成员函数

五、基本操作示例

#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();}

七、注意事项

1. 访问前检查空栈：调用top()或pop()前务必使用empty()检查

   if(!st.empty()){intval=st.top();st.pop();}

2. 栈不能直接遍历：需要遍历时，可以复制一份或使用临时栈

   voidprintStack(stack<int>s){// 值传递，不修改原栈while(!s.empty()){cout<<s.top()<<" ";s.pop();}}

3. 性能考虑：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;}