企业官网建设流程全解析

C++ STL 栈详解：stack 的使用、经典题目与简单模拟实现

前言

在数据结构中，栈算是比较容易理解的一种结构。

它的规则很简单：最后放进去的元素，最先被取出来。

这种特点通常称为：

后进先出 Last In First Out LIFO

C++ 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的底层容器是deque：

std::stack<int>

近似于：

std::stack<int,std::deque<int>>

也可以显式指定其他容器：

std::stack<int,std::vector<int>>s1;std::stack<int,std::list<int>>s2;

只要底层容器支持：

back()push_back()pop_back()

就可以用来封装栈。

三、stack 的常用接口

使用stack需要包含头文件：

#include<stack>

常用接口如下：

一个最基本的例子：

#include<iostream>#include<stack>usingnamespacestd;intmain(){stack<int>st;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 为什么不返回被删除的元素？

很多初学者会写出下面的代码：

intvalue=st.pop();

但这段代码无法通过编译。

原因是：

pop()

只负责删除栈顶元素，返回类型是void。

如果需要获取栈顶元素，应该先调用top()，再调用pop()：

intvalue=st.top();st.pop();

完整写法：

if(!st.empty()){intvalue=st.top();st.pop();cout<<value<<'\n';}

这种接口设计把“读取”和“删除”分成了两个操作：

top()：读取栈顶 pop()：删除栈顶

代码的行为也会更加明确。

五、访问栈顶前先判断 empty

空栈中没有栈顶元素，因此不要直接对空栈调用：

st.top();st.pop();

更稳妥的写法是：

if(!st.empty()){cout<<st.top()<<'\n';st.pop();}

遍历并清空整个栈时，可以这样写：

while(!st.empty()){cout<<st.top()<<" ";st.pop();}

需要注意，这种遍历会删除栈中的所有元素。

如果不想修改原栈，可以先复制一份：

stack<int>copy=st;while(!copy.empty()){cout<<copy.top()<<" ";copy.pop();}

六、stack 为什么没有迭代器？

vector、list这些容器都能使用迭代器遍历：

for(autoit=v.begin();it!=v.end();++it){cout<<*it<<" ";}

但stack没有提供：

begin()end()

这是刻意设计的结果。

栈的核心规则是：

只能从栈顶访问元素。

如果允许我们直接遍历、修改中间元素，栈的约束就失去了意义。

因此，stack只公开栈顶相关接口，不公开底层容器的迭代器。

这也是容器适配器的重要特点：它不是把底层容器的所有功能原样暴露出来，而是主动隐藏不符合当前数据结构规则的接口。

七、用栈实现数据逆序

栈天然适合处理逆序问题。

例如，将数组中的元素反向输出：

#include<iostream>#include<stack>#include<vector>usingnamespacestd;intmain(){vector<int>nums{1,2,3,4,5};stack<int>st;for(intvalue:nums){st.push(value);}while(!st.empty()){cout<<st.top()<<" ";st.pop();}return0;}

输出：

5 4 3 2 1

八、经典应用：括号匹配

给定一个只包含下面几种字符的字符串：

() [] {}

判断括号是否正确匹配。

例如：

()[]{} 正确 ([{}]) 正确 ([)] 错误 (( 错误

基本思路是：

1. 遇到左括号就入栈；
2. 遇到右括号，检查它是否和栈顶左括号匹配；
3. 匹配成功就弹出栈顶；
4. 最后栈必须为空。

代码如下：

#include<stack>#include<string>usingnamespacestd;boolisValid(conststring&s){stack<char>st;for(charch:s){if(ch=='('||ch=='['||ch=='{'){st.push(ch);}else{if(st.empty()){returnfalse;}chartop=st.top();boolmatched=(top=='('&&ch==')')||(top=='['&&ch==']')||(top=='{'&&ch=='}');if(!matched){returnfalse;}st.pop();}}returnst.empty();}

为什么要检查最后的栈是否为空？

因为字符串可能是：

(((

整个过程中没有出现错误的右括号，但左括号始终没有被匹配，因此结果仍然应该是false。

九、经典应用：最小栈

普通栈只能快速得到栈顶元素。

现在增加一个要求：

在 O(1) 时间内得到栈中的最小值

最直接的思路是每次遍历整个栈，但这样查询最小值需要 O(N)。

更合适的办法是使用两个栈：

_elem：保存所有元素 _min ：保存当前阶段的最小值

实现如下：

#include<stack>usingnamespacestd;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:stack<int>_elem;stack<int>_min;};

这里需要注意：

value<=_min.top()

不能只写成：

value<_min.top()

因为栈里可能存在重复的最小值。

例如依次压入：

3 1 1

两个1都应该记录到_min中。否则弹出一个1后，程序会误以为栈中已经没有最小值1。

十、经典应用：逆波兰表达式求值

逆波兰表达式也叫后缀表达式。

普通中缀表达式：

(2 + 1) * 3

对应的逆波兰表达式是：

2 1 + 3 *

求值规则：

• 遇到数字就入栈；
• 遇到运算符，就弹出两个数字；
• 计算结果重新入栈；
• 最后栈顶就是答案。

代码如下：

#include<stack>#include<string>#include<vector>usingnamespacestd;intevalRPN(constvector<string>&tokens){stack<int>st;for(conststring&token:tokens){if(token!="+"&&token!="-"&&token!="*"&&token!="/"){st.push(stoi(token));continue;}intright=st.top();st.pop();intleft=st.top();st.pop();if(token=="+"){st.push(left+right);}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进行封装。

下面实现一个简单版本：

#include<cassert>#include<cstddef>#include<deque>namespacebit{template<classT,classContainer=std::deque<T>>classstack{public:stack()=default;voidpush(constT&value){_container.push_back(value);}voidpop(){assert(!_container.empty());_container.pop_back();}T&top(){assert(!_container.empty());return_container.back();}constT&top()const{assert(!_container.empty());return_container.back();}std::size_tsize()const{return_container.size();}boolempty()const{return_container.empty();}private:Container _container;};}

测试代码：

#include<iostream>intmain(){bit::stack<int>st;st.push(10);st.push(20);st.push(30);while(!st.empty()){std::cout<<st.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

错误：

stack<int>st;cout<<st.top();

应先判断：

if(!st.empty()){cout<<st.top();}

2. 认为 pop 会返回元素

错误：

intvalue=st.pop();

正确：

intvalue=st.top();st.pop();

3. 最小栈没有处理重复最小值

错误：

if(value<_min.top())

更稳妥：

if(_min.empty()||value<=_min.top())

4. 逆波兰表达式操作数顺序写反

正确顺序：

intright=st.top();st.pop();intleft=st.top();st.pop();

5. 试图直接遍历 stack

stack没有公开迭代器。需要查看全部元素时，可以复制一份栈，然后不断读取和弹出。

十四、stack 的常见使用场景

栈适合处理“最近状态优先”的问题，例如：

函数调用栈 递归过程 括号匹配 表达式求值 浏览器返回 撤销操作 深度优先搜索 单调栈 字符串和数据逆序

判断一个问题是否适合栈，可以先问一句：

当前处理是否依赖最近加入、但尚未完成的元素？

如果答案是肯定的，通常可以考虑栈。

总结

stack的接口不多，但应用范围很广。

学习时需要重点掌握：

1. 栈遵循后进先出规则 2. push、pop 和 top 都操作栈顶 3. pop 只删除元素，不返回元素 4. 空栈不能直接调用 top 和 pop 5. stack 是容器适配器，没有公开迭代器 6. 默认底层容器是 deque 7. 栈适合处理逆序、匹配、回退和最近状态问题

从模拟实现中也能看到，stack并没有重新实现一套复杂的数据存储结构，而是把底层容器已有的几个接口重新组合起来。