前言
前面学习 vector、list 等 STL 容器时，它们给我的感觉都是：
容器自己负责存储数据，同时又向外提供各种操作数据的接口。
但是学习到 stack 以后，会发现它有些不一样。
例如：
cpp
复制代码
stack
我们不能像 vector 那样：
cpp
复制代码
st[0];
也不能使用迭代器从头到尾遍历。
它允许我们做的事情非常有限：
cpp
复制代码
push()
pop()
top()
empty()
size()
一开始可能会觉得：
为什么 stack 的功能反而这么少？
但继续往下学习以后就会发现，这恰恰是 stack 的设计思想。
它并不是为了提供丰富的数据访问方式，而是主动限制操作，只允许我们遵守：
cpp
复制代码
后进先出
Last In First Out
LIFO
这篇博客就从 stack 的基本使用开始，一直理解到它的底层实现以及几个经典算法题。
一、stack 到底是什么？为什么叫容器适配器？
在正式使用 stack 之前，我觉得首先要搞懂一个非常重要的词：
容器适配器（Container Adapter）
我们以前学过：
cpp
复制代码
vector
list
deque
这些容器本身就负责真正的数据存储。
而 stack 的思路不一样。
它更像是在一个已有容器外面套了一层壳，然后把底层容器原本丰富的接口限制起来，只留下符合"栈"规则的操作。
可以简单理解成：
复制代码
stack
↓
┌────────────────┐
│ push() │
│ pop() │
用户 → │ top() │
│ empty() │
│ size() │
└────────────────┘
↓
vector / deque / list
↓
真正存数据
所以 stack 最值得理解的一点是：
它重点解决的不是"数据存在哪里"，而是"允许用户以什么方式访问这些数据"。
例如底层如果是 vector：
复制代码
vector
原本可以：
复制代码
v.push_back(10);
v.pop_back();
v[0];
v.begin();
v.end();
但是把它包装成一个栈以后，我们希望用户只能：
复制代码
st.push(10);
st.pop();
st.top();
这样就保证了所有操作都符合栈的规则。
除了 stack 之外，我们后面还会接触：
cpp
复制代码
queue
priority_queue
它们同样属于容器适配器。
区别主要在于数据访问规则不同：
复制代码
stack
后进先出
queue
先进先出
priority_queue
按照优先级取元素
所以容器适配器给我的感觉就是：
同样的底层容器，通过不同的接口限制，可以表现成不同的数据结构。
二、stack 的核心特点与基本接口
栈最核心的特点只有四个字：
后进先出
英文为：
复制代码
LIFO
Last In First Out
可以想象成一摞盘子。
假设依次放入：
复制代码
10
20
30
过程大概是：
复制代码
第一次：
┌────┐
│ 10 │ ← 栈顶
└────┘
第二次：
┌────┐
│ 20 │ ← 栈顶
├────┤
│ 10 │
└────┘
第三次：
┌────┐
│ 30 │ ← 栈顶
├────┤
│ 20 │
├────┤
│ 10 │
└────┘
如果现在出栈，第一个出去的一定是：
复制代码
30
然后才是：
复制代码
20
10
所以：
复制代码
最后进去的
↓
最先出来
使用 STL 中的 stack 需要：
cpp
复制代码
#include
定义：
cpp
复制代码
stack
常用接口其实不多。
push ------ 入栈
cpp
复制代码
st.push(10);
st.push(20);
st.push(30);
此时：
cpp
复制代码
栈顶
↓
30
20
10
top ------ 获取栈顶元素
cpp
复制代码
cout << st.top() << endl;
输出：
复制代码
30
注意：
cpp
复制代码
top()
只是访问栈顶，并不会删除元素。
pop ------ 删除栈顶元素
cpp
复制代码
st.pop();
执行之后：
cpp
复制代码
栈顶
↓
20
10
这里一个非常容易犯的错误是：
cpp
复制代码
cout << st.pop();
这是不行的。
因为：
pop() 只负责删除元素，不负责把被删除的元素返回出来。
如果既想得到栈顶元素，又想删除它，需要写：
复制代码
int x = st.top();
st.pop();
cout << x << endl;
也就是：
复制代码
先 top()
再 pop()
size ------ 获取元素个数
cpp
复制代码
cout << st.size() << endl;
empty ------ 判断栈是否为空
cpp
复制代码
if (st.empty())
{
cout << "stack is empty" << endl;
}
通常真正使用时，经常写：
cpp
复制代码
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
例如：
cpp
复制代码
#include
#include
using namespace std;
int main()
{
stack
st.push(5);
st.push(15);
st.push(25);
st.push(35);
cout << "size = " << st.size() << endl;
cout << "top = " << st.top() << endl;
st.pop();
cout << "pop以后：" << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
return 0;
}
输出：
cpp
复制代码
size = 4
top = 35
pop以后：
25 15 5
正好体现：
cpp
复制代码
5 → 15 → 25 → 35
是入栈顺序，而：
cpp
复制代码
35 → 25 → 15 → 5
是出栈顺序。
这里还有两个需要特别注意的地方。
第一个：
cpp
复制代码
st.top();
之前最好确保：
cpp
复制代码
!st.empty()
因为空栈不存在栈顶元素。
第二个：
stack 没有给我们提供普通容器那样的迭代器遍历接口。
我们不能：
cpp
复制代码
for (auto e : st)
{
}
因为如果能够随便访问栈中任意位置，反而破坏了栈这种数据结构的抽象。
要想依次获取元素，通常只能：
cpp
复制代码
top()
↓
pop()
↓
top()
↓
pop()
不断从栈顶操作。
三、stack 为什么可以使用不同的底层容器？
接下来就是我觉得 stack 最有意思的地方。
标准库中的 stack 本质上可以理解成类似：
cpp
复制代码
template
class stack
{
// ...
};
也就是说它实际上有两个模板参数：
cpp
复制代码
T
↓
栈里存什么类型的数据
Container
↓
真正用什么容器保存数据
如果我们只写：
cpp
复制代码
stack
实际上使用默认底层容器：
cpp
复制代码
deque
也可以自己指定：
cpp
复制代码
stack
stack
stack
这三个都可以实现"栈"。
为什么？
关键不是容器叫什么名字，而是：
这个容器能不能提供 stack 所需要的能力。
stack 最基本只需要在一端操作。
我们需要：
cpp
复制代码
push_back()
完成入栈。
需要：
cpp
复制代码
pop_back()
完成出栈。
需要：
cpp
复制代码
back()
访问栈顶。
再配合：
cpp
复制代码
size()
empty()
就已经足够完成 stack 的主要功能了。
因此：
cpp
复制代码
vector
deque
list
都能够满足要求。
那既然 vector 也能实现，为什么标准库默认选择 deque？
这里首先要知道两者底层结构存在差异。
vector 更强调：
复制代码
连续内存空间
空间不足时可能需要重新申请更大的连续空间，再移动或复制已有元素。
而 deque 并不要求所有元素都存放在一整块连续内存中，它采用更适合两端扩展的结构。
对于 stack 来说，我们根本不需要：
复制代码
随机访问第 100 个元素
我们真正关心的是：
复制代码
尾插
尾删
访问尾元素
所以 deque 非常适合作为 stack 的默认底层容器。
不过这里不要理解成：
vector 不能实现 stack。
实际上：
cpp
复制代码
stack
完全没问题。
区别只是底层存储策略不同。
这里也能看出 STL 设计中一个很重要的思想：
上层结构只提出"我需要什么能力"，至于下面由谁完成，可以通过模板替换。
这也是后面自己模拟实现 stack 时最核心的地方。
四、自己模拟实现一个 stack
如果前面容器适配器的思想真正理解了，自己实现 stack 其实会发现代码非常短。
因为我们根本不需要自己重新实现：
复制代码
扩容
内存管理
节点连接
空间释放
这些复杂工作全部交给底层容器。
我们只需要进行接口转换。
例如自己写一个：
cpp
复制代码
namespace my
{
template
class Stack
{
public:
void push(const T& value)
{
_con.push_back(value);
}
void pop()
{
assert(!_con.empty());
_con.pop_back();
}
T& top()
{
assert(!_con.empty());
return _con.back();
}
const T& top() const
{
assert(!_con.empty());
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
这里最关键的一行其实不是任何一个成员函数，而是：
cpp
复制代码
Container _con;
它说明：
Stack 自己并没有重新写一套底层存储，而是直接"拥有"一个容器。
然后：
cpp
复制代码
push()
内部调用：
cpp
复制代码
_con.push_back();
cpp
复制代码
pop()
内部调用：
cpp
复制代码
_con.pop_back();
cpp
复制代码
top()
内部调用：
cpp
复制代码
_con.back();
整个过程可以画成：
cpp
复制代码
用户调用
Stack::push(x)
↓
_con.push_back(x)
↓
底层容器完成真正的数据插入
所以模拟实现 stack 以后，我对"容器适配器"这个名字就明显理解得更深了。
它真正做的是：
复用底层容器，然后重新包装接口。
这里还有一个容易忽略的地方：
cpp
复制代码
T& top()
为什么还要再写：
cpp
复制代码
const T& top() const
因为如果存在一个 const 栈：
cpp
复制代码
const my::Stack
const 对象不能调用普通的非 const 成员函数。
所以需要提供：
cpp
复制代码
const T& top() const
让 const 对象也能够读取栈顶元素，同时不能通过返回值修改它。
我们还可以测试不同底层容器：
cpp
复制代码
#include
#include
#include
#include
#include
using namespace std;
namespace my
{
template
class Stack
{
public:
void push(const T& value)
{
_con.push_back(value);
}
void pop()
{
assert(!_con.empty());
_con.pop_back();
}
T& top()
{
assert(!_con.empty());
return _con.back();
}
const T& top() const
{
assert(!_con.empty());
return _con.back();
}
size_t size() const
{
return _con.size();
}
bool empty() const
{
return _con.empty();
}
private:
Container _con;
};
}
int main()
{
my::Stack
my::Stack
my::Stack
for (int i = 1; i <= 5; ++i)
{
s1.push(i * 10);
s2.push(i * 10);
s3.push(i * 10);
}
cout << s1.top() << endl;
cout << s2.top() << endl;
cout << s3.top() << endl;
return 0;
}
三个结果都是：
cpp
复制代码
50
50
50
这就说明：
stack 的逻辑规则没有变，变化的只是它背后真正负责存储的容器。
这也是模板 + 容器适配器结合以后非常灵活的地方。
五、stack 的经典算法应用
只会：
cpp
复制代码
push
pop
top
还只是学会 stack 的语法。
真正能够理解什么时候应该使用栈，才算把这个数据结构学明白。
这一节课里有三个很典型的应用。
1. 最小栈
普通栈可以：
cpp
复制代码
top()
在常数时间得到栈顶。
现在希望增加一个功能：
cpp
复制代码
getMin()
要求每次都能快速得到当前整个栈中的最小值。
最直观的想法可能是：
cpp
复制代码
每次调用 getMin
把栈里面的元素全部找一遍
但是这样每次都需要扫描很多元素。
更好的办法是：
再准备一个辅助栈，专门记录最小值。
假设依次压入：
cpp
复制代码
5
3
7
2
主栈：
cpp
复制代码
栈顶
↓
2
7
3
5
辅助最小栈可以变成：
cpp
复制代码
栈顶
↓
2
3
5
辅助栈的栈顶永远就是：
cpp
复制代码
当前最小值
代码可以这样实现：
cpp
复制代码
#include
#include
using namespace std;
class MinStack
{
public:
void push(int value)
{
_data.push(value);
if (_mins.empty() || value <= _mins.top())
{
_mins.push(value);
}
}
void pop()
{
assert(!_data.empty());
if (_data.top() == _mins.top())
{
_mins.pop();
}
_data.pop();
}
int top() const
{
assert(!_data.empty());
return _data.top();
}
int getMin() const
{
assert(!_mins.empty());
return _mins.top();
}
private:
stack
stack
};
这里有一个细节：
cpp
复制代码
value <= _mins.top()
为什么是：
复制代码
<=
而不是：
复制代码
<
因为可能出现重复最小值。
例如：
复制代码
3
3
如果第二个 3 不进入最小栈，那么弹掉第一个栈顶 3 时，最小值信息就可能丢失。
所以重复的最小值也应该被记录。
2. 判断一个出栈序列是否合法
假设入栈顺序为：
复制代码
1 2 3 4 5
现在给你一个出栈顺序：
复制代码
4 5 3 2 1
问：
这个顺序有没有可能通过正常 push/pop 得到？
这里最适合的办法不是自己凭感觉分析，而是：
真的准备一个栈，把整个过程模拟一遍。
思路就是：
复制代码
按顺序入栈
↓
每放入一个元素
↓
检查栈顶是否等于当前希望弹出的数字
↓
相等就不断弹出
例如：
cpp
复制代码
push 1
push 2
push 3
push 4
当前栈顶 = 4
目标出栈 = 4
所以 pop
接下来目标变成 5。
继续：
复制代码
push 5
于是：
复制代码
top = 5
继续 pop。
最后如果整个弹出序列都能成功匹配，就说明这个序列合法。
代码可以写得比较直接：
cpp
复制代码
#include
#include
using namespace std;
bool IsValidPopOrder(
const vector
const vector
{
if (pushOrder.size() != popOrder.size())
return false;
stack
size_t popIndex = 0;
for (int value : pushOrder)
{
st.push(value);
while (!st.empty()
&& popIndex < popOrder.size()
&& st.top() == popOrder[popIndex])
{
st.pop();
++popIndex;
}
}
return st.empty();
}
这个题给我的一个启发是：
当题目描述本身就是一个动态过程时，"按照规则真实模拟"往往比硬找数学规律更加自然。
3. 逆波兰表达式求值
第三个经典问题是：
后缀表达式求值。
例如普通表达式：
复制代码
(2 + 1) * 3
转换成逆波兰表达式以后：
复制代码
2 1 + 3 *
特点是：
运算符写在操作数后面。
处理规则非常适合栈。
遇到数字：
复制代码
压栈
遇到运算符：
复制代码
弹出两个数字
↓
运算
↓
结果重新压栈
例如：
复制代码
2 1 + 3 *
先读取：
复制代码
2
stack:
2
再读取：
复制代码
1
stack:
1
2
遇到：
复制代码
+
弹出：
复制代码
right = 1
left = 2
计算：
复制代码
2 + 1 = 3
重新压栈。
然后读取另一个：
复制代码
3
此时栈中：
复制代码
3
3
遇到：
复制代码
*
得到：
复制代码
3 * 3 = 9
最终答案就是：
复制代码
9
代码：
cpp
复制代码
#include
#include
#include
using namespace std;
class Solution
{
public:
int evalRPN(vector
{
stack
for (const string& token : tokens)
{
if (token == "+"
|| token == "-"
|| token == "*"
|| token == "/")
{
int right = st.top();
st.pop();
int left = st.top();
st.pop();
if (token == "+")
st.push(left + right);
else if (token == "-")
st.push(left - right);
else if (token == "*")
st.push(left * right);
else
st.push(left / right);
}
else
{
st.push(stoi(token));
}
}
return st.top();
}
};
这里一个非常容易写错的地方是：
cpp
复制代码
int right = st.top();
st.pop();
int left = st.top();
st.pop();
为什么顺序不能反？
因为：
复制代码
8 2 -
表示的是：
复制代码
8 - 2
而不是：
复制代码
2 - 8
由于栈后进先出：
复制代码
先弹出来的是右操作数
后弹出来的是左操作数
对：
复制代码
+
*
可能暂时看不出问题，因为它们满足交换律。
但：
复制代码
-
/
左右顺序一反，答案马上就错了。
六、学完 stack 以后真正应该掌握什么？
学完这一部分以后，如果只记住：
cpp
复制代码
stack
st.push();
st.pop();
st.top();
我觉得还是比较表面。
真正重要的是把它背后的逻辑串起来。
整个 stack 可以这样理解：
cpp
复制代码
stack
↓
后进先出 LIFO
↓
只允许操作栈顶
↓
push / pop / top
↓
本身不负责重新发明存储结构
↓
使用已有容器作为底层
↓
deque / vector / list
↓
通过模板实现底层容器可替换
↓
形成"容器适配器"
我觉得其中最值得理解的一句话就是：
stack 不是在创造一种新的底层存储方式，而是在已有容器的基础上规定一种新的使用规则。
这也是为什么自己模拟实现 stack 时，代码会非常简单：
cpp
复制代码
push()
↓
push_back()
pop()
↓
pop_back()
top()
↓
back()
真正复杂的：
复制代码
内存申请
扩容
节点管理
元素存储
都已经由：
复制代码
vector
deque
list
帮我们完成了。
而 stack 做的事情是：
通过封装隐藏底层细节，只把符合"栈"语义的接口开放出来。
这其实也是一个非常典型的 C++ 设计思想：
复制代码
复用已有能力
+
限制不需要的接口
+
提供符合当前场景的新抽象
最后从算法角度再看，什么时候应该想到栈？
我目前会重点关注下面几类关键词：
复制代码
最近加入的东西优先处理
回退 / 回溯
配对匹配
表达式计算
模拟压栈弹栈过程
需要保存"之前状态"
例如：
复制代码
括号匹配
函数调用栈
逆波兰表达式
单调栈
DFS中的部分场景
撤销操作
都可以继续往 stack 的方向思考。
所以这一节真正让我从"会使用 STL 接口"往前走了一步：
不只是知道 stack 怎么用，还开始理解为什么 STL 要把它设计成一个容器适配器，以及这种设计方式是怎么通过模板和已有容器实现代码复用的。