C++ STL：stack、queue、priority_queue 与容器适配器详解
文章目录
- C++ STL：stack、queue、priority_queue 与容器适配器详解
- 三、最小栈
- 四、栈的弹出压入序列
- 五、逆波兰表达式求值
- 六、stack 的模拟实现
- 七、queue
- 八、queue 的底层容器
- 九、queue 的模拟实现
- 十、priority_queue
- 十一、priority_queue 与堆
- 十二、大堆和小堆
- 十三、自定义类型使用 priority_queue
- 十四、priority_queue 解决第 K 大元素
- 十五、什么是容器适配器
- 十六、stack 和 queue 的底层结构
- 十七、deque
- 十八、deque 并不是真正连续的空间
- 十九、deque 的缺陷
- 二十、为什么 stack 和 queue 默认使用 deque
- 二十一、stack 的完整模拟实现
- 二十二、queue 的完整模拟实现
- 二十三、stack、queue、priority_queue 对比
一、stack
1.1 stack 的基本概念
stack 是一种**后进先出（LIFO）**的数据结构
也就是说：
Last In First Out
最后进入栈中的元素，最先被取出
可以把栈理解成一摞盘子
入栈
↓
┌───┐
│ 3 │ ← 栈顶
├───┤
│ 2 │
├───┤
│ 1 │
└───┘
出栈时只能从最上面取
因此 stack 不支持随机访问，不能像 vector 一样通过下标访问中间元素
常用接口：
| 接口 | 作用 |
|---|---|
stack() | 构造空栈 |
empty() | 判断栈是否为空 |
size() | 获取栈中元素个数 |
top() | 获取栈顶元素 |
push() | 将元素压入栈顶 |
pop() | 删除栈顶元素 |
其中最常用的就是：
s.push(x);
s.pop();
s.top();
s.empty();
s.size();
需要注意：
s.pop();
只是删除栈顶元素，并不会返回被删除的元素
如果需要先获取栈顶元素，再删除：
int x = s.top();
s.pop();
二、stack 的使用
使用 stack 需要包含头文件：
#include <stack>
基本使用：
stack<int> s;
s.push(1);
s.push(2);
s.push(3);
此时：
栈顶
↓
3
2
1
执行：
cout << s.top() << endl;
得到：
3
执行：
s.pop();
此时：
栈顶
↓
2
1
三、最小栈
普通 stack 可以在 O(1) 时间内获取栈顶元素，但是如果要求：
随时获取当前栈中的最小值
普通 stack 无法直接完成
一种经典方法是使用两个栈
stack<int> _elem;
stack<int> _min;
其中：
_elem
保存正常的栈元素
_min
保存当前栈中的最小值
3.1 入栈
假设依次加入：
5 3 7 2
可以按照下面的方式维护 _min
_elem _min
5 5
3 3
7 3
2 2
每次入栈时：
void push(int x)
{
_elem.push(x);
if (_min.empty() || x <= _min.top())
_min.push(x);
}
关键代码：
if (_min.empty() || x <= _min.top())
如果当前元素小于等于 _min 栈顶的元素，就把它也压入 _min
为什么使用 <= 而不是 <
因为最小值可能出现多次
例如：
5
3
3
此时 _min：
3
3
5
如果连续弹出两个 3，需要让 _min 中的两个 3 也分别被弹出
3.2 出栈
void pop()
{
if (_min.top() == _elem.top())
_min.pop();
_elem.pop();
}
例如：
_elem _min
7 3
3 3
5 5
此时弹出 3
由于：
_elem.top() == _min.top()
所以 _min 中的 3 也需要删除
最终：
_elem _min
7 5
5
3.3 获取最小值
int getMin()
{
return _min.top();
}
因为 _min 的栈顶始终保存当前最小值，所以获取最小值的时间复杂度为：
O(1)
完整结构可以理解成：
class MinStack
{
public:
void push(int x)
{
_elem.push(x);
if (_min.empty() || x <= _min.top())
_min.push(x);
}
void pop()
{
if (_min.top() == _elem.top())
_min.pop();
_elem.pop();
}
int top()
{
return _elem.top();
}
int getMin()
{
return _min.top();
}
private:
stack<int> _elem;
stack<int> _min;
};
核心思想就是：
一个栈保存所有数据，另一个栈专门维护当前最小值
四、栈的弹出压入序列
一个经典问题：
给定一个入栈序列，判断一个出栈序列是否合法
例如：
入栈：
1 2 3 4 5
如果出栈：
4 5 3 2 1
是可以实现的
过程：
1入栈
2入栈
3入栈
4入栈
4出栈
5入栈
5出栈
3出栈
2出栈
1出栈
但是如果要求：
4 3 5 1 2
则无法实现
模拟栈解决
核心思想：
按照入栈序列不断入栈，只要栈顶等于当前要求的出栈元素，就立即出栈
代码：
bool IsPopOrder(vector<int> pushV, vector<int> popV)
{
if (pushV.size() != popV.size())
return false;
int outIdx = 0;
int inIdx = 0;
stack<int> s;
while (outIdx < popV.size())
{
while (s.empty() || s.top() != popV[outIdx])
{
if (inIdx < pushV.size())
s.push(pushV[inIdx++]);
else
return false;
}
s.pop();
outIdx++;
}
return true;
}
这个题最重要的是理解：
while (s.empty() || s.top() != popV[outIdx])
只要当前栈顶不是目标出栈元素，就继续从入栈序列中拿元素进栈
如果所有元素都已经入栈，栈顶仍然不是目标元素，那么说明这个出栈序列无法实现
五、逆波兰表达式求值
逆波兰表达式也叫后缀表达式
例如普通表达式：
3 + 4
逆波兰表达式：
3 4 +
再比如：
3 + 4 * 5
可以写成：
3 4 5 * +
这种表达式非常适合使用栈处理
5.1 基本思想
从左到右遍历表达式
如果遇到数字：
入栈
如果遇到运算符：
取出两个栈顶元素
进行计算
把结果重新压入栈
例如：
3 4 +
过程：
3入栈
4入栈
遇到+
取出4
取出3
3 + 4 = 7
7重新入栈
5.2 为什么减法和除法要注意顺序
假设栈中：
3
4
栈顶是：
4
因此：
int right = s.top();
s.pop();
int left = s.top();
s.pop();
计算：
left - right
而不能写成：
right - left
例如：
3 4 -
正确结果：
3 - 4 = -1
除法也是同样的道理
left / right
5.3 代码
int evalRPN(vector<string>& tokens)
{
stack<int> s;
for (size_t i = 0; i < tokens.size(); ++i)
{
string& str = tokens[i];
if (!(str == "+" ||
str == "-" ||
str == "*" ||
str == "/"))
{
s.push(atoi(str.c_str()));
}
else
{
int right = s.top();
s.pop();
int left = s.top();
s.pop();
switch (str[0])
{
case '+':
s.push(left + right);
break;
case '-':
s.push(left - right);
break;
case '*':
s.push(left * right);
break;
case '/':
s.push(left / right);
break;
}
}
}
return s.top();
}
六、stack 的模拟实现
stack 本身是一种容器适配器
因此可以使用其他容器作为它的底层容器
例如使用 vector
#include <vector>
namespace bite
{
template<class T>
class stack
{
public:
stack()
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top() const
{
return _c.back();
}
size_t size() const
{
return _c.size();
}
bool empty() const
{
return _c.empty();
}
private:
vector<T> _c;
};
}
可以发现：
push()
对应：
vector::push_back()
pop()
对应：
vector::pop_back()
top()
对应：
vector::back()
因此：
只要底层容器能够支持
push_back()和pop_back()，就可以用来实现 stack
例如：
vector
list
deque
都可以
七、queue
7.1 queue 的基本概念
queue 是一种**先进先出（FIFO）**的数据结构
即：
First In First Out
最先进入队列的元素最先出去
例如：
入队 →
1 2 3 4
↑ ↑
队头 队尾
出队时：
1
先出去
然后：
2
再出去
因此队列与栈最大的区别：
stack：
后进先出
queue：
先进先出
7.2 queue 的常用接口
| 接口 | 作用 |
|---|---|
queue() | 构造空队列 |
empty() | 判断队列是否为空 |
size() | 获取元素个数 |
front() | 获取队头元素 |
back() | 获取队尾元素 |
push() | 从队尾入队 |
pop() | 从队头出队 |
例如：
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
此时：
队头 队尾
↓ ↓
1 2 3
执行：
q.pop();
删除：
1
剩下：
2 3
八、queue 的底层容器
queue 本身也是一种容器适配器
底层容器需要支持：
empty()
size()
front()
back()
push_back()
pop_front()
标准库中：
deque
list
都可以满足要求
默认情况下：
queue<int>
使用：
deque<int>
作为底层容器
九、queue 的模拟实现
因为 queue 同时需要：
尾插
头删
如果使用 vector，头删需要移动大量元素，因此效率较低
所以可以使用 list 模拟
#include <list>
namespace bite
{
template<class T>
class queue
{
public:
queue()
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& back()
{
return _c.back();
}
const T& back() const
{
return _c.back();
}
T& front()
{
return _c.front();
}
const T& front() const
{
return _c.front();
}
size_t size() const
{
return _c.size();
}
bool empty() const
{
return _c.empty();
}
private:
list<T> _c;
};
}
对应关系：
queue::push()
↓
list::push_back()
queue::pop()
↓
list::pop_front()
queue::front()
↓
list::front()
queue::back()
↓
list::back()
十、priority_queue
priority_queue 的基本概念
priority_queue 是优先级队列
普通 queue 遵循：
先进先出
而 priority_queue 不按照进入顺序出队
它按照元素的优先级决定谁先出来
默认情况下：
priority_queue<int>
是大堆
也就是说：
top()
返回当前最大的元素
例如：
priority_queue<int> q;
q.push(3);
q.push(7);
q.push(2);
q.push(9);
那么：
q.top()
得到：
9
十一、priority_queue 与堆
priority_queue 底层默认使用：
vector
然后利用堆算法维护堆结构
因此可以把：
priority_queue
理解为：
堆 + 容器适配器接口
常用接口：
| 接口 | 作用 |
|---|---|
empty() | 判断是否为空 |
size() | 获取元素个数 |
top() | 获取堆顶元素 |
push() | 插入元素 |
pop() | 删除堆顶元素 |
其中：
top()
只是查看堆顶
而：
pop()
才是真正删除堆顶
十二、大堆和小堆
默认：
priority_queue<int>
是大堆
例如：
priority_queue<int> q;
q.push(3);
q.push(2);
q.push(7);
q.push(6);
q.push(0);
q.push(4);
q.push(1);
q.push(9);
q.push(8);
q.push(5);
cout << q.top() << endl;
输出：
9
创建小堆
如果希望最小的元素位于堆顶，可以使用：
greater<int>
priority_queue<int, vector<int>, greater<int>> q;
此时：
q.top()
得到的是最小值
例如：
priority_queue<int, vector<int>, greater<int>> q;
q.push(3);
q.push(7);
q.push(2);
q.push(9);
cout << q.top() << endl;
结果：
2
因此：
priority_queue<int>
表示大堆
priority_queue<int, vector<int>, greater<int>>
表示小堆
十三、自定义类型使用 priority_queue
如果 priority_queue 中存储的是自定义类型，就需要告诉它：
两个对象之间应该如何比较
例如定义：
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d) const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d) const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
private:
int _year;
int _month;
int _day;
};
然后：
priority_queue<Date> q1;
默认构造大堆，因此需要提供：
operator<
如果使用：
priority_queue<Date, vector<Date>, greater<Date>> q2;
则需要提供：
operator>
十四、priority_queue 解决第 K 大元素
例如：
数组：
3 2 1 5 6 4
要求：
第 2 大元素
可以把所有元素放入大堆：
priority_queue<int> p(nums.begin(), nums.end());
此时：
top() = 最大值
不断删除最大的元素：
for (int i = 0; i < k - 1; ++i)
{
p.pop();
}
最后：
return p.top();
对于：
3 2 1 5 6 4
建立大堆后：
6
5
4
3
2
1
删除一次最大值：
5
4
3
2
1
此时：
top()
就是第二大的元素：
5
十五、什么是容器适配器
适配器的核心思想就是：
将一个已有类的接口转换成另外一种接口
STL 中的：
stack
queue
priority_queue
都属于容器适配器
它们本身并不是传统意义上的底层数据结构
而是：
已有容器
↓
进行封装
↓
限制和重新组织接口
↓
形成新的数据结构
例如：
vector
↓
封装
↓
stack
stack 不允许用户直接访问中间元素，只提供：
push()
pop()
top()
这样就形成了后进先出的特性
十六、stack 和 queue 的底层结构
stack 和 queue 默认使用：
deque
作为底层容器
例如：
template<class T, class Con = deque<T>>
class stack
{
...
};
其中：
Con
就是底层容器类型
因此实际上：
stack<int>
可以理解成：
stack<int, deque<int>>
也可以指定：
stack<int, vector<int>>
或者：
stack<int, list<int>>
只要底层容器能够满足 stack 所需要的接口即可
十七、deque
deque 的基本特点
deque 可以理解为：
双端队列
它允许在头部和尾部进行插入和删除
头部 尾部
↓ ↓
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴───┴───┘
↑ ↑
头删头插 尾删尾插
与 vector 相比：
deque
头插效率高
因为不需要像 vector 那样搬移大量元素
与 list 相比：
deque
空间利用率更高
十八、deque 并不是真正连续的空间
这是理解 deque 时非常重要的一点
deque 看起来像一段连续空间：
1 2 3 4 5 6 7 8
但实际上它由多个连续的小空间组成
可以理解成：
┌───────┐
│ 1 2 3 │
└───────┘
↓
┌───────┐
│ 4 5 6 │
└───────┘
↓
┌───────┐
│ 7 8 9 │
└───────┘
因此：
整体看起来连续
实际内部是分段连续
为了让用户感觉像是在访问连续空间，deque 的迭代器需要处理不同小块之间的切换
这也是 deque 迭代器实现比较复杂的原因
十九、deque 的缺陷
虽然 deque 有很多优点，但它也存在明显缺陷
最主要的问题：
不适合频繁遍历
因为 deque 实际上是分段连续空间
遍历过程中，迭代器需要不断判断当前是否已经到达某一段空间的边界
因此遍历效率不如真正连续的 vector
所以实际使用线性容器时：
需要频繁随机访问和遍历
↓
vector
需要频繁插入和删除
↓
list
而 deque 的典型应用之一就是作为：
stack
queue
的底层容器
二十、为什么 stack 和 queue 默认使用 deque
这是这部分内容中非常重要的一点
20.1 stack 的需求
stack 只需要：
push_back()
pop_back()
因此：
vector
list
deque
都可以作为底层容器
20.2 queue 的需求
queue 需要：
push_back()
pop_front()
因此：
list
deque
比较适合
vector 的 pop_front() 需要移动大量元素，因此不适合作为 queue 的底层容器
20.3 为什么最终选择 deque
因为：
stack
不需要遍历，只需要在固定的一端操作
queue
也不需要遍历，只需要在两端进行操作
而 deque：
头部插入删除效率高
尾部插入删除效率高
扩容时不需要搬移大量数据
空间利用率比 list 高
同时又避开了 deque 最明显的缺陷：
不适合频繁遍历
因为：
stack
queue
本身就不提供迭代器，也不需要进行遍历
所以：
deque 的优点
+
stack / queue 不需要遍历
↓
非常适合作为 stack / queue 的默认底层容器
二十一、stack 的完整模拟实现
#include <deque>
namespace bite
{
template<class T, class Con = deque<T>>
class stack
{
public:
stack()
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top() const
{
return _c.back();
}
size_t size() const
{
return _c.size();
}
bool empty() const
{
return _c.empty();
}
private:
Con _c;
};
}
这里最值得注意的是：
template<class T, class Con = deque<T>>
意味着：
T
↓
stack 中存储的数据类型
Con
↓
stack 使用的底层容器
默认：
Con = deque<T>
因此：
stack<int>
实际上相当于：
stack<int, deque<int>>
当然也可以指定：
stack<int, vector<int>>
或者：
stack<int, list<int>>
二十二、queue 的完整模拟实现
#include <deque>
namespace bite
{
template<class T, class Con = deque<T>>
class queue
{
public:
queue()
{}
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& back()
{
return _c.back();
}
const T& back() const
{
return _c.back();
}
T& front()
{
return _c.front();
}
const T& front() const
{
return _c.front();
}
size_t size() const
{
return _c.size();
}
bool empty() const
{
return _c.empty();
}
private:
Con _c;
};
}
核心对应关系：
queue::push()
↓
_c.push_back()
queue::pop()
↓
_c.pop_front()
queue::front()
↓
_c.front()
queue::back()
↓
_c.back()
因此 queue 的底层容器只需要满足相应接口即可
二十三、stack、queue、priority_queue 对比
| 容器适配器 | 核心特点 | 默认底层容器 | 主要操作 |
|---|---|---|---|
stack | 后进先出 | deque | 一端进出 |
queue | 先进先出 | deque | 一端进一端出 |
priority_queue | 按优先级出队 | vector | 堆顶进出 |
从数据结构角度理解：
stack
↓
后进先出
↓
适合处理具有后进先出特点的问题
queue
↓
先进先出
↓
适合处理具有先进先出特点的问题
priority_queue
↓
堆
↓
快速获取当前最大值或最小值
其中 stack 和 queue 都属于容器适配器，而 priority_queue 底层则通过 vector 加堆算法维护优先级结构
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2501_93810221/article/details/167080815
