【C++】一篇吃透容器适配器三件套：从stack/queue/priority_queue到deque底层
很多人第一次看到
priority_queue<int, vector<int>, greater<int>>这种类型声明时，脑子里只剩下一个问号：这东西到底包了几层？再加上deque这个“伪连续空间”一起登场，更是容易看了就忘。这篇文章会一步步把接口、例题、模拟实现和底层结构串在一起，让你下次再写这行代码时，不只是能编译通过，而是真正知道自己在用什么。
目录
4.4 为什么选择deque作为stack和queue的底层默认容器
1. stack的介绍和使用
1.1 stack的介绍
| 函数说明 | 接口说明 |
|---|---|
stack() | 构造一个空栈 |
empty() | 判断栈是否为空 |
size() | 返回栈中元素个数 |
top() | 返回栈顶元素的引用 |
push() | 把元素val压入栈顶 |
pop() | 把栈顶元素弹出（移除，不返回值） |
std::stack是一个后进先出（LIFO）的容器适配器：
-
只允许在一端（栈顶）进行插入和删除；
-
不支持遍历（没有迭代器），只有
push/pop/top这几个固定动作； -
底层可以用
vector、list、deque等线性结构来实现。
1.2 stack的使用
例题：
-
最小栈；
-
判断一个出栈序列是否可能；
-
逆波兰表达式求值。
1.2.1 最小栈（MinStack）
题目大意：
实现一个栈，除了正常的
push/pop/top以外，还要在O(1)时间拿到当前栈内的最小值getMin()。
思路：
-
用一个正常栈
_elem保存所有元素； -
再用一个辅助栈
_min保存“到当前位置为止的最小值链”：-
每次压入新元素
x时：-
_elem.push(x)； -
若
_min为空或x <= _min.top()，就_min.push(x)；
-
-
每次弹出时：
-
如果
_elem.top()等于_min.top()，辅助栈也要一起pop；
-
-
-
这样
_min.top()始终就是当前栈内最小值。
代码示例：
#include <stack>
class MinStack
{
public:
void push(int x)
{
//只要压栈,先入_elem
_elem.push(x);
//如果_min为空或者x<=当前最小值,同步压入_min
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:
//保存所有元素
std::stack<int> _elem;
//保存到当前位置为止的最小值链
std::stack<int> _min;
};
1.2.2 栈的弹出压入序列
题目大意：
给定一个入栈序列
pushV和一个出栈序列popV，判断popV是否可能是pushV在某种合法入栈/出栈顺序下产生的弹出序列。
思路：
-
准备一个辅助栈
s，用它模拟真实入栈出栈过程； -
维护两个下标：
-
inIdx：当前入栈序列pushV用到了哪里； -
outIdx：当前要匹配的出栈序列popV位置；
-
-
对每个
popV[outIdx]：-
如果栈为空或栈顶不等于
popV[outIdx]，就从pushV中继续push入栈；-
如果入栈序列已经用完还对不上，直接返回
false；
-
-
一旦栈顶等于
popV[outIdx]，就pop一次，outIdx++；
-
-
最后如果能顺利匹配完整个
popV，说明出栈序列合法。
代码示例：
#include <vector>
#include <stack>
using namespace std;
class Solution
{
public:
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 < (int)popV.size())
{
//如果栈空或者栈顶!=当前要弹出的值,就继续入栈
while (s.empty() || s.top() != popV[outIdx])
{
if (inIdx < (int)pushV.size())
{
s.push(pushV[inIdx++]);
}
else
{
//入栈序列已经用完还对不上,说明不可能
return false;
}
}
//栈顶和当前要弹出的值相等,弹出
s.pop();
++outIdx;
}
return true;
}
};
1.2.3 逆波兰表达式求值
逆波兰表达式（RPN，Reverse Polish Notation）是一种不需要括号的表达式形式，例如：
-
中缀表达式：
(2 + 1) * 3 -
后缀表达式：
["2", "1", "+", "3", "*"]
求值规则：
-
从左到右扫描令牌；
-
如果遇到数字，就压栈；
-
如果遇到操作符：
-
从栈中弹出两个数
right和left； -
按操作符计算
left op right； -
把结果再压回栈；
-
-
扫描结束后，栈顶就是最终结果。
代码示例：
#include <vector>
#include <stack>
#include <string>
#include <cstdlib>
using namespace std;
class Solution
{
public:
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 '/':
//题目说明了不存在除数为0的情况
s.push(left / right);
break;
}
}
}
return s.top();
}
};
1.3 stack的模拟实现
观察stack的接口可以发现：它只需要在一端尾插/尾删，并能访问栈顶即可。因此任何支持push_back/pop_back/back的容器，都可以拿来当stack的底层，比如vector。
下面是一个用std::vector封装的简化版stack：
代码示例：
#include <vector>
namespace my
{
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:
std::vector<T> _c;
};
}
2. queue的介绍和使用
2.1 queue的介绍
| 函数说明 | 接口说明 |
|---|---|
queue() | 构造空队列 |
empty() | 检测队列是否为空 |
size() | 返回队列中有效元素个数 |
front() | 返回队头元素的引用 |
back() | 返回队尾元素的引用 |
push() | 在队尾插入元素val（入队） |
pop() | 删除队头元素（出队，不返回值） |
std::queue是一个先进先出（FIFO）的容器适配器：从队尾入，从队头出。
概念：
-
队列是一种容器适配器，用于在先进先出（FIFO）场景中操作元素：一端插入，另一端提取；
-
自己不直接存元素，而是把某个底层容器包起来，对外暴露
push/pop/front/back等接口； -
底层容器需要支持以下操作：
-
empty()：检测是否为空； -
size()：返回有效元素个数； -
front()：访问队头； -
back()：访问队尾； -
push_back()：尾部插入； -
pop_front()：头部删除；
-
-
标准容器
deque和list都满足这些要求； -
默认底层容器是
deque，如果不指定，queue<int>就等价于queue<int, deque<int>>。
2.2 queue的使用
代码示例：
#include <iostream>
#include <queue>
using namespace std;
void TestQueueUse()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout << "front:" << q.front() << endl;
cout << "back:" << q.back() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
2.3 queue的模拟实现
队列的接口需要头删+尾插，如果用vector来封装，每次pop()都要把前面的元素搬一遍，效率很低；用list或deque就比较合适。
下面是一个用std::list做底层的简化queue：
代码示例：
#include <list>
namespace my
{
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:
std::list<T> _c;
};
}
3. priority_queue的介绍和使用
3.1 priority_queue的介绍
priority_queue也是一个容器适配器(堆)：
-
它保证
top()永远是内部元素里“最大（或最小）”的那个； -
插入元素可以随时做，但取元素只能从
top()取； -
底层会用
make_heap/push_heap/pop_heap等算法维护堆结构。
| 函数声明 | 接口说明 |
|---|---|
priority_queue() / (first,last) | 构造一个空的优先级队列或用区间元素构造一个优先级队列 |
empty() | 判断是否为空 |
size() | 返回有效元素个数 |
top() | 返回队列中“优先级最高”的元素引用（默认是最大值） |
push(x) | 插入元素x |
pop() | 删除“优先级最高”的元素（堆顶元素） |
总结：
-
priority_queue保证第一个元素始终是最大元素（默认）； -
底层容器可以是任意支持随机访问迭代器的容器（如
vector/deque）； -
默认底层容器是
vector； -
优先级队列在内部会自动调用
make_heap/push_heap/pop_heap维护堆； -
默认比较方式是
less<T>，所以默认是大根堆（最大值优先）。
3.2 priority_queue的使用
3.2.1 基本类型：大堆和小堆
代码示例：
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
void TestPriorityQueueInt()
{
vector<int> v{ 3, 2, 7, 6, 0, 4, 1, 9, 8, 5 };
//默认是大堆,底层用less比较
priority_queue<int> q1;
for (auto& e : v)
{
q1.push(e);
}
cout << q1.top() << endl; //最大元素
//如果要小堆,第三个模板参数换成greater
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl; //最小元素
}
-
第一种写法：
priority_queue<int>，默认大根堆； -
第二种写法：
priority_queue<int, vector<int>, greater<int>>，改成小根堆。
3.2.2 自定义类型
对于自定义类型，需要提供比较规则，默认使用less<T>，即需要operator<。如果要用greater<T>，则需要operator>。
代码示例：
#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
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);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
void TestPriorityQueueDate()
{
//大堆,需要提供<的重载
priority_queue<Date> q1;
q1.push(Date(2018, 10, 29));
q1.push(Date(2018, 10, 28));
q1.push(Date(2018, 10, 30));
cout << q1.top() << endl;
//小堆,需要提供>的重载
priority_queue<Date, vector<Date>, greater<Date>> q2;
q2.push(Date(2018, 10, 29));
q2.push(Date(2018, 10, 28));
q2.push(Date(2018, 10, 30));
cout << q2.top() << endl;
}
3.3 在OJ中的使用
3.3.1 数组中第K个大的元素。
思路：
-
把所有元素丢进一个大根堆；
-
然后弹出前
k-1个最大值； -
此时堆顶就是第
k大的元素。
代码示例：
#include <vector>
#include <queue>
using namespace std;
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
//将数组中的元素先放入大根堆
priority_queue<int> p(nums.begin(), nums.end());
//弹出前k-1个
for (int i = 0; i < k - 1; ++i)
{
p.pop();
}
return p.top();
}
};
3.4 priority_queue的模拟实现
从结构上看，优先级队列底层就是一个堆 + 底层容器 + 比较器的组合：
-
容器负责存放元素；
-
堆算法负责维护堆序性；
-
比较器负责决定谁的优先级更高。
4. 容器适配器
4.1 什么是适配器
“适配器”是一种设计模式：把一个类的接口转换成客户希望的另一种接口。这样原来的类可以继续复用，只是对外长得不一样了。
STL里：
-
stack/queue/priority_queue都不直接管理底层数据结构； -
它们只是把
vector/list/deque这些容器“包装一下”，对外提供一个更符合使用场景的接口：-
stack对外：push/pop/top，隐藏遍历； -
queue对外：push/pop/front/back； -
priority_queue对外：push/pop/top，但内部是堆结构。
-
4.2 STL标准库中stack和queue的底层结构
虽然stack/queue也可以存元素，但在STL的分类里，它们不叫“容器”，而叫“容器适配器”。
原因就是：它们只是对其他容器的接口进行包装，把某些操作“隐藏掉”，只保留特定场景需要的那些。
标准库里的声明：
//stack
template<class T, class Container = std::deque<T>>
class stack;
//queue
template<class T, class Container = std::deque<T>>
class queue;
总结：
-
stack<int>其实是stack<int, deque<int>>； -
queue<int>其实是queue<int, deque<int>>； -
它们默认都是基于
deque实现的； -
可以改成
vector或list，只要满足接口要求即可。
4.3 deque的介绍
4.3.1 deque的原理
deque（double-ended queue，双端队列）是一种双开口的伪连续空间数据结构：
-
支持在头尾两端进行插入和删除，时间复杂度O(1)；
-
和
vector相比：头插效率高，不需要整体搬移元素； -
和
list相比：空间利用率高，因为底层使用的是“分段连续空间”。
底层不是一整段连续内存，而是类似“动态二维数组”：
-
上层有一个
map（控制数组），存放指向“缓冲区（buffer）”的指针； -
每个缓冲区是一小段连续空间；
-
整个
deque就是多个缓冲区拼接起来形成的“逻辑连续空间”。
迭代器为了维持伪连续假象，会记录：
-
当前所在缓冲区指针
node； -
缓冲区的
first/last边界； -
当前元素位置
cur。
4.3.2 deque的缺陷
优点：
-
与vector比较：头部插入/删除不需要搬全体元素，扩容也不需要整体搬移；
-
与list比较：整体上仍然是“分段连续”，空间利用率更高，不用额外存
prev/next指针。
致命缺陷：
不适合频繁遍历。
原因在于：
-
迭代器每次
++都要检查是否越过当前缓冲区边界； -
一旦跨界，就要切换到下一块缓冲区；
-
这套检查逻辑会让遍历比
vector慢不少。
在很多实际场景中，线性结构往往需要频繁遍历，因此：
-
需要高效遍历+随机访问时，优先用
vector； -
需要频繁插入删除时，优先考虑
list； -
deque使用场景相对少一些，比较典型的用途就是作为stack和queue的底层容器。
4.4 为什么选择deque作为stack和queue的底层默认容器
-
不需要遍历
-
stack和queue本身就没有迭代器，对外只提供固定几个接口； -
它们的使用场景只在栈顶/队头/队尾操作，不会整段遍历；
-
因此
deque遍历慢的缺点在这里完全不怕。
-
-
扩容和两端操作更高效
-
stack只需要在一端不断push_back/pop_back； -
queue既要push_back又要pop_front； -
对于这两类操作，
deque比vector更省成本，比list更节省空间； -
尤其是元素大量增长时，
deque扩容不需要整体搬移既有数据。
-
让
stack/queue默认使用deque，刚好利用了deque的优点，又完美避开了“遍历慢”的缺点。
4.5 STL标准库中对于stack和queue的模拟实现
4.5.1 stack的模拟实现
代码示例：
#include <deque>
namespace my
{
template<class T, class Con = std::deque<T>>
//template<class T, class Con = std::vector<T>>
//template<class T, class Con = std::list<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;
};
}
思路：
-
只要
Con提供push_back/pop_back/back/size/empty这些接口，就能拿来当stack的底层； -
默认用
deque，也可以把模板注释放开换成vector或list来实验。
4.5.2 queue的模拟实现
代码示例：
#include <deque>
//#include <list>
namespace my
{
template<class T, class Con = std::deque<T>>
//template<class T, class Con = std::list<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;
};
}
完
更多推荐
38
0- 0
已为社区贡献3条内容
所有评论(0)