C STL 栈详解stack 的使用、经典题目与简单模拟实现 星恒随风个人主页❄️ 个人专栏《指针合集》《C语言基础》《数据结构》《机器学习导论》《前端基础》《python基础》《C从入门到入土》✨ 数据即知识压缩即智能文章目录C STL 栈详解stack 的使用、经典题目与简单模拟实现前言一、什么是栈二、stack 是容器适配器三、stack 的常用接口四、pop 为什么不返回被删除的元素五、访问栈顶前先判断 empty六、stack 为什么没有迭代器七、用栈实现数据逆序八、经典应用括号匹配九、经典应用最小栈十、经典应用逆波兰表达式求值十一、简单模拟实现 stack十二、为什么默认底层容器是 deque1. 栈不需要连续存储2. vector 扩容时可能搬移元素3. deque 支持高效尾插和尾删十三、常见错误整理1. 对空栈调用 top 或 pop2. 认为 pop 会返回元素3. 最小栈没有处理重复最小值4. 逆波兰表达式操作数顺序写反5. 试图直接遍历 stack十四、stack 的常见使用场景总结前言在数据结构中栈算是比较容易理解的一种结构。它的规则很简单最后放进去的元素最先被取出来。这种特点通常称为后进先出 Last In First Out LIFOC STL 已经提供了stack使用起来并不复杂。但只记住push()和pop()还不够我们还需要理解栈为什么只能访问栈顶pop()为什么不返回被删除的元素stack为什么没有迭代器什么是容器适配器为什么 STL 默认使用deque作为底层容器如何用已有容器简单模拟一个栈一、什么是栈栈是一种操作受限的线性数据结构。假设依次把下面三个元素压入栈中1 2 3栈中的状态可以画成栈顶 ↓ ┌───┐ │ 3 │ ├───┤ │ 2 │ ├───┤ │ 1 │ └───┘此时最先弹出的元素是3然后是2最后才是1。整个过程是入栈顺序1 2 3 出栈顺序3 2 1栈只允许在同一端插入和删除元素这一端称为栈顶。常见操作包括push压栈 pop 出栈 top 访问栈顶二、stack 是容器适配器在 STL 中stack严格来说并不是一个独立的序列容器而是一个容器适配器。容器适配器可以简单理解为在已有容器外面包一层只开放符合某种数据结构规则的接口。例如deque本身支持头尾插入、头尾删除和随机访问但把它封装成stack后只允许使用push()pop()top()empty()size()这样就把一个功能较多的容器限制成了“后进先出”的栈。其大致结构可以理解成stack 对外接口 ↓ push / pop / top ↓ 底层容器 deque默认情况下std::stack的底层容器是dequestd::stackint近似于std::stackint,std::dequeint也可以显式指定其他容器std::stackint,std::vectorints1;std::stackint,std::listints2;只要底层容器支持back()push_back()pop_back()就可以用来封装栈。三、stack 的常用接口使用stack需要包含头文件#includestack常用接口如下接口作用stack()构造一个空栈empty()判断栈是否为空size()返回栈中元素个数top()返回栈顶元素的引用push(x)将元素压入栈中pop()删除栈顶元素emplace(...)在栈顶直接构造元素swap()交换两个栈一个最基本的例子#includeiostream#includestackusingnamespacestd;intmain(){stackintst;st.push(10);st.push(20);st.push(30);cout栈顶元素st.top()\n;cout元素个数st.size()\n;st.pop();cout出栈后的栈顶st.top()\n;return0;}四、pop 为什么不返回被删除的元素很多初学者会写出下面的代码intvaluest.pop();但这段代码无法通过编译。原因是pop()只负责删除栈顶元素返回类型是void。如果需要获取栈顶元素应该先调用top()再调用pop()intvaluest.top();st.pop();完整写法if(!st.empty()){intvaluest.top();st.pop();coutvalue\n;}这种接口设计把“读取”和“删除”分成了两个操作top()读取栈顶 pop()删除栈顶代码的行为也会更加明确。五、访问栈顶前先判断 empty空栈中没有栈顶元素因此不要直接对空栈调用st.top();st.pop();更稳妥的写法是if(!st.empty()){coutst.top()\n;st.pop();}遍历并清空整个栈时可以这样写while(!st.empty()){coutst.top() ;st.pop();}需要注意这种遍历会删除栈中的所有元素。如果不想修改原栈可以先复制一份stackintcopyst;while(!copy.empty()){coutcopy.top() ;copy.pop();}六、stack 为什么没有迭代器vector、list这些容器都能使用迭代器遍历for(autoitv.begin();it!v.end();it){cout*it ;}但stack没有提供begin()end()这是刻意设计的结果。栈的核心规则是只能从栈顶访问元素。如果允许我们直接遍历、修改中间元素栈的约束就失去了意义。因此stack只公开栈顶相关接口不公开底层容器的迭代器。这也是容器适配器的重要特点它不是把底层容器的所有功能原样暴露出来而是主动隐藏不符合当前数据结构规则的接口。七、用栈实现数据逆序栈天然适合处理逆序问题。例如将数组中的元素反向输出#includeiostream#includestack#includevectorusingnamespacestd;intmain(){vectorintnums{1,2,3,4,5};stackintst;for(intvalue:nums){st.push(value);}while(!st.empty()){coutst.top() ;st.pop();}return0;}输出5 4 3 2 1八、经典应用括号匹配给定一个只包含下面几种字符的字符串() [] {}判断括号是否正确匹配。例如()[]{} 正确 ([{}]) 正确 ([)] 错误 (( 错误基本思路是遇到左括号就入栈遇到右括号检查它是否和栈顶左括号匹配匹配成功就弹出栈顶最后栈必须为空。代码如下#includestack#includestringusingnamespacestd;boolisValid(conststrings){stackcharst;for(charch:s){if(ch(||ch[||ch{){st.push(ch);}else{if(st.empty()){returnfalse;}chartopst.top();boolmatched(top(ch))||(top[ch])||(top{ch});if(!matched){returnfalse;}st.pop();}}returnst.empty();}为什么要检查最后的栈是否为空因为字符串可能是(((整个过程中没有出现错误的右括号但左括号始终没有被匹配因此结果仍然应该是false。九、经典应用最小栈普通栈只能快速得到栈顶元素。现在增加一个要求在 O(1) 时间内得到栈中的最小值最直接的思路是每次遍历整个栈但这样查询最小值需要 O(N)。更合适的办法是使用两个栈_elem保存所有元素 _min 保存当前阶段的最小值实现如下#includestackusingnamespacestd;classMinStack{public:voidpush(intvalue){_elem.push(value);if(_min.empty()||value_min.top()){_min.push(value);}}voidpop(){if(_elem.empty()){return;}if(_elem.top()_min.top()){_min.pop();}_elem.pop();}inttop()const{return_elem.top();}intgetMin()const{return_min.top();}boolempty()const{return_elem.empty();}private:stackint_elem;stackint_min;};这里需要注意value_min.top()不能只写成value_min.top()因为栈里可能存在重复的最小值。例如依次压入3 1 1两个1都应该记录到_min中。否则弹出一个1后程序会误以为栈中已经没有最小值1。十、经典应用逆波兰表达式求值逆波兰表达式也叫后缀表达式。普通中缀表达式(2 1) * 3对应的逆波兰表达式是2 1 3 *求值规则遇到数字就入栈遇到运算符就弹出两个数字计算结果重新入栈最后栈顶就是答案。代码如下#includestack#includestring#includevectorusingnamespacestd;intevalRPN(constvectorstringtokens){stackintst;for(conststringtoken:tokens){if(token!token!-token!*token!/){st.push(stoi(token));continue;}intrightst.top();st.pop();intleftst.top();st.pop();if(token){st.push(leftright);}elseif(token-){st.push(left-right);}elseif(token*){st.push(left*right);}else{st.push(left/right);}}returnst.top();}这里取数顺序不能写反。对于减法和除法left - right left / right先弹出的元素是右操作数后弹出的元素才是左操作数。十一、简单模拟实现 stack从接口可以看出栈需要的底层操作并不多尾插 尾删 访问尾部元素 判断是否为空 获取元素个数因此可以用vector、deque或list进行封装。下面实现一个简单版本#includecassert#includecstddef#includedequenamespacebit{templateclassT,classContainerstd::dequeTclassstack{public:stack()default;voidpush(constTvalue){_container.push_back(value);}voidpop(){assert(!_container.empty());_container.pop_back();}Ttop(){assert(!_container.empty());return_container.back();}constTtop()const{assert(!_container.empty());return_container.back();}std::size_tsize()const{return_container.size();}boolempty()const{return_container.empty();}private:Container _container;};}测试代码#includeiostreamintmain(){bit::stackintst;st.push(10);st.push(20);st.push(30);while(!st.empty()){std::coutst.top() ;st.pop();}return0;}输出30 20 10模拟实现的核心并不复杂push()-push_back()pop()-pop_back()top()-back()这正是容器适配器的基本思想。十二、为什么默认底层容器是 deque既然vector也能实现栈为什么 STL 默认选择deque可以从几个方面理解。1. 栈不需要连续存储栈只操作尾部不需要依赖连续内存也不需要随机访问。2. vector 扩容时可能搬移元素当vector容量不足时通常需要申请新空间 搬移原有元素 释放旧空间而deque使用分段存储增长时通常不需要把全部元素整体搬到另一块连续空间。3. deque 支持高效尾插和尾删栈需要的核心操作正好是push_back()pop_back()back()这些都是deque擅长的操作。因此deque能满足栈的操作需求也能避开vector扩容时大规模搬移数据的问题。十三、常见错误整理1. 对空栈调用 top 或 pop错误stackintst;coutst.top();应先判断if(!st.empty()){coutst.top();}2. 认为 pop 会返回元素错误intvaluest.pop();正确intvaluest.top();st.pop();3. 最小栈没有处理重复最小值错误if(value_min.top())更稳妥if(_min.empty()||value_min.top())4. 逆波兰表达式操作数顺序写反正确顺序intrightst.top();st.pop();intleftst.top();st.pop();5. 试图直接遍历 stackstack没有公开迭代器。需要查看全部元素时可以复制一份栈然后不断读取和弹出。十四、stack 的常见使用场景栈适合处理“最近状态优先”的问题例如函数调用栈 递归过程 括号匹配 表达式求值 浏览器返回 撤销操作 深度优先搜索 单调栈 字符串和数据逆序判断一个问题是否适合栈可以先问一句当前处理是否依赖最近加入、但尚未完成的元素如果答案是肯定的通常可以考虑栈。总结stack的接口不多但应用范围很广。学习时需要重点掌握1. 栈遵循后进先出规则 2. push、pop 和 top 都操作栈顶 3. pop 只删除元素不返回元素 4. 空栈不能直接调用 top 和 pop 5. stack 是容器适配器没有公开迭代器 6. 默认底层容器是 deque 7. 栈适合处理逆序、匹配、回退和最近状态问题从模拟实现中也能看到stack并没有重新实现一套复杂的数据存储结构而是把底层容器已有的几个接口重新组合起来。