STL stack 入门基础讲解(附例题一、stack 基础概念栈stack是一种后进先出的线性数据结构所有插入、删除、访问操作都只能在栈顶进行。C STL 中的stack属于容器适配器底层默认基于deque实现也可以手动指定vector、list作为底层容器。它封装了栈的标准操作使用简单且效率稳定。1. 头文件与定义使用前需要引入头文件#includestackusingnamespacestd;// 栈位于std命名空间定义方式stack数据类型栈名;// 示例stackintst;// 存储int类型的栈stackcharst_c;// 存储char类型的栈stackstringst_s;// 存储string类型的栈2. 常用成员函数所有操作时间复杂度均为O(1)函数作用注意事项push(x)将元素x压入栈顶无返回值pop()弹出栈顶元素无返回值栈为空时调用会出现未定义行为top()返回栈顶元素的引用栈为空时调用会出错empty()判断栈是否为空空返回true非空返回falsesize()返回栈中元素的个数返回值为无符号整数类型基础使用示例stackintst;st.push(1);// 栈: [1]st.push(2);// 栈: [1, 2]coutst.top();// 输出 2st.pop();// 弹出2栈: [1]coutst.size();// 输出 1coutst.empty();// 输出 0 (false)二、栈的经典应用场景栈的核心特性是“后进先出”非常适合处理嵌套结构、最近匹配、顺序反转类问题常见题型包括括号匹配系列单/多种括号合法性校验、最少删除得到合法括号序列表达式处理中缀表达式转后缀、表达式求值、括号拆解与展开递归模拟用栈模拟系统调用栈实现非递归DFS、回溯算法单调栈进阶求解下一个更大元素、柱状图最大矩形等问题撤销/回溯浏览器后退、编辑器撤销等功能的底层逻辑三、例题1最少删除合法括号序列题目链接牛客竞赛 - 括号序列题意简述给定一个只包含(和)的字符串求最少删除多少个括号能让剩余序列成为合法括号序列空串也视为合法。解题思路合法括号序列的核心规则任意前缀中左括号数量 ≥ 右括号数量且整体左右括号总数相等。我们使用贪心栈的思路求解最少删除数遍历字符串用栈记录未匹配的左括号遇到左括号(直接压入栈等待后续右括号匹配遇到右括号)若栈非空弹出栈顶左括号完成一对匹配若栈为空该右括号无法匹配必须删除答案计数 1遍历结束后栈中剩余的左括号均无法匹配也需要删除答案加上栈的大小该策略能匹配到最多的合法括号对因此得到的删除数就是最小值。参考代码与解析#includebits/stdc.husingnamespacestd;signedmain(){ios::sync_with_stdio(false);cin.tie(0);// 加速输入应对大数据量intt;cint;while(t--){intn,ans0;string s;cinns;stackcharst;for(charc:s){if(c(){st.push(c);// 左括号入栈等待匹配}else{if(st.empty()){ans;// 无左括号匹配删除该右括号}else{st.pop();// 匹配成功弹出栈顶左括号}}}ansst.size();// 剩余未匹配的左括号都要删除coutans\n;}return0;}样例模拟输入样例())(()长度6第1个字符(入栈栈[ ( ]第2个字符)栈非空弹出栈空ans0第3个字符)栈空ans → ans1第4个字符(入栈栈[ ( ]第5个字符(入栈栈[ (, ( ]第6个字符)栈非空弹出栈[ ( ]遍历结束ans 栈大小1 → 最终答案为2与样例输出一致。四、例题2算式拆解2025PTA-L2真题PTA官网https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7题意简述给定一个完全由括号包裹的算式格式为(对象 操作符 对象)对象可以是数字或另一个嵌套算式。要求按执行顺序从内层到外层输出每一对括号内的运算表达式。解题思路算式的执行顺序是“内层括号先执行”正好匹配栈“后进先出”的特性遍历字符串每个字符非右括号)直接压入栈遇到右括号)时说明找到最内层的一对括号从栈顶不断弹出字符直到遇到左括号(将弹出的字符拼接成字符串由于弹出顺序是逆序的反转字符串后输出即为当前内层括号的运算式最后弹出左括号(完成该层处理遍历全程会自动按从内到外的顺序输出所有运算即算式的执行顺序。参考代码与解析#includebits/stdc.husingnamespacestd;intmain(){string s;cins;stackcharst;for(inti0;is.size();i){if(s[i])){string tmp;// 弹出直到遇到左括号while(st.top()!(){tmpst.top();st.pop();}reverse(tmp.begin(),tmp.end());// 反转恢复正序couttmp\n;st.pop();// 弹出左括号}else{st.push(s[i]);// 非右括号直接入栈}}return0;}样例模拟输入样例(((23)*4)-(5/(6*7)))遍历到第一个)时弹出3、、2拼接为32反转后输出23继续遍历到第二个)时弹出4、*拼接为4*反转后输出*4遍历到第三个)时弹出7、*、6拼接为7*6反转后输出6*7遍历到第四个)时弹出/、5拼接为/5反转后输出5/遍历到最后一个)时弹出-输出-输出结果与样例完全一致。五、总结stack是入门级STL容器操作少、逻辑简单核心是掌握“后进先出”的特性。括号匹配、表达式拆解是栈最基础的应用题核心思路都是利用栈处理“嵌套、就近匹配”的逻辑。使用栈时务必注意边界判断调用pop()和top()前先检查empty()避免越界出错。
郑州网站建设
网页设计
企业官网
![[Android ] 闲言App v6.8 文字文艺软件 最新版](http://pic.xiahunao.cn/yaotu/[Android ] 闲言App v6.8 文字文艺软件 最新版)
