容器适配器深度解析：从STL的stack、queue到优先队列的底层实现
文章目录
容器适配器深度解析：从STL的stack、queue到优先队列的底层实现
1. 栈的介绍和使用
1.1 栈的介绍
栈（stack）是一种后进先出（LIFO）的数据结构，它允许在一端进行插入和删除操作。在C++ STL中，stack是一个容器适配器，提供了一组特定的成员函数来访问其元素。
1.2 栈的使用
| 函数 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测stack是否为空 |
| size() | 返回stack中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素val压入stack中 |
| pop() | 将stack中尾部的元素弹出 |
最小栈实现
最小栈能够在O(1)时间内获取栈中的最小元素。
classMinStack{public:voidpush(int x){// 压栈时，先将元素保存到_elem _elem.push(x);// 如果x小于_min中栈顶的元素，将x再压入_min中if(_min.empty()|| x <= _min.top()) _min.push(x);}voidpop(){// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除if(_min.top()== _elem.top()) _min.pop(); _elem.pop();}inttop(){return _elem.top();}intgetMin(){return _min.top();}private: std::stack<int> _elem;// 保存栈中的元素 std::stack<int> _min;// 保存栈的最小值};栈的弹出压入序列
验证一个序列是否是栈的弹出序列。
classMinStack{public:MinStack(){}voidpush(int val){ st.push(val);if(minst.empty()||minst.top()>=val){ minst.push(val);}}voidpop(){if(st.top()==minst.top()){ minst.pop();} st.pop();}inttop(){return st.top();}intgetMin(){return minst.top();}private: stack<int> st; stack<int> minst;};逆波兰表达式求值
classSolution{public:intevalRPN(vector<string>& tokens){ stack<int> s;for(size_t i =0; i < tokens.size();++i){ string& str = tokens[i];// str为数字if(!("+"== str ||"-"== str ||"*"== str ||"/"== str)){ s.push(atoi(str.c_str()));}else{// str为操作符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();}};1.3 stack的模拟实现
以下是使用容器适配器模式实现的stack，支持自定义底层容器（默认使用deque）：
#pragmaonce#include<deque>namespace bit {// container适配器实现stacktemplate<classT,classContainer= deque<T>>classstack{public:voidpush(const T& x){ _con.push_back(x);}voidpop(){ _con.pop_back();}const T&top()const{return _con.back();} size_t size()const{return _con.size();}boolempty(){return _con.empty();}private: Container _con;};}2. 队列的介绍和使用
2.1 队列的介绍
队列是一种先进先出（FIFO）的数据结构，元素从队尾入队列，从队头出队列。在C++ STL中，queue是一个容器适配器。
queue的特点：
- 队列是一种容器适配器，专门用于在FIFO上下文（先进先出）中操作
- 元素从队尾入队列，从队头出队列
- 底层容器可以是deque或list，默认使用deque
2.2 queue的使用
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空 |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素val入队列 |
| pop() | 将队头元素出队列 |
2.3 queue的模拟实现
使用容器适配器模式实现的queue，支持自定义底层容器：
#pragmaonce#include<deque>namespace bit {template<classT,classContainer= deque<T>>classqueue{public:voidpush(const T& x){ _con.push_back(x);}voidpop(){ _con.pop_front();}const T&front()const{return _con.front();}const T&back()const{return _con.back();} size_t size()const{return _con.size();}boolempty(){return _con.empty();}private: Container _con;};}3. 优先队列的介绍和使用
3.1 priority_queue的介绍
优先队列是一种容器适配器，它的第一个元素总是它所包含的元素中最大的（默认大堆）。
priority_queue的特点：
- 第一个元素总是最大的（默认大堆）
- 类似于堆，可以随时插入元素，只能检索最大堆元素
- 默认使用vector作为底层容器
- 支持随机访问迭代器
3.2 priority_queue的使用
| 函数声明 | 接口说明 |
|---|---|
| priority_queue() | 构造一个空的优先级队列 |
| priority_queue(first, last) | 用迭代器范围构造优先级队列 |
| empty() | 检测优先级队列是否为空 |
| top() | 返回优先级队列中最大(最小)元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素 |
使用示例：
#include<vector>#include<queue>#include<functional>// greater算法的头文件voidTestPriorityQueue(){// 默认情况下，创建的是大堆，其底层按照小于号比较 vector<int> v{3,2,7,6,0,4,1,9,8,5}; priority_queue<int> q1;for(auto& e : v) q1.push(e); cout << q1.top()<< endl;// 输出9// 创建小堆，将第三个模板参数换成greater比较方式 priority_queue<int, vector<int>, greater<int>>q2(v.begin(), v.end()); cout << q2.top()<< endl;// 输出0}注意：
- 默认情况下，priority_queue是大堆
- 如果要创建小堆，需要指定第三个模板参数为
greater<T> - 如果存放自定义类型，需要在自定义类型中提供
>或<的重载
3.3 priority_queue的模拟实现
以下是完整的优先队列模拟实现，包含大堆和小堆支持：
#pragmaonce#include<vector>namespace bit {// 仿函数类：Less（升序/大堆）template<classT>classLess{public:booloperator()(const T& x,const T& y){return x < y;}};// 仿函数类：Greater（降序/小堆）template<classT>classGreater{public:booloperator()(const T& x,const T& y){return x > y;}};// 优先队列实现// 模板参数：// T - 元素类型// Container - 底层容器，默认vector<T>// Compare - 比较器，默认Less<T>（大堆）template<classT,classContainer= vector<T>,classCompare= Less<T>>classpriority_queue{public:// 向上调整（插入时使用）voidAdjustUp(int child){ Compare com; size_t parent =(child -1)/2;while(child >0){// 使用仿函数进行比较if(com(_con[parent], _con[child])){swap(_con[child], _con[parent]); child = parent; parent =(child -1)/2;}else{break;}}}// 向下调整（删除时使用）voidAdjustDown(int parent){int child = parent *2+1; Compare com;while(child < _con.size()){// 找出较大（或较小）的孩子if(child +1< _con.size()&&com(_con[child], _con[child +1])){++child;}// 如果父节点小于（或大于）孩子节点，交换if(com(_con[parent], _con[child])){swap(_con[child], _con[parent]); parent = child; child = parent *2+1;}else{break;}}}// 插入元素voidpush(const T& x){ _con.push_back(x);AdjustUp(_con.size()-1);}// 删除堆顶元素voidpop(){swap(_con[0], _con[_con.size()-1]); _con.pop_back();AdjustDown(0);}// 获取堆顶元素const T&top(){return _con[0];}// 获取元素个数 size_t size()const{return _con.size();}// 判断是否为空boolempty()const{return _con.empty();}private: Container _con;};}4. 容器适配器
4.1 什么是适配器
适配器是一种设计模式，将一个类的接口转换成客户希望的另外一个接口。
4.2 STL标准库中stack和queue的底层结构
stack和queue在STL中称为容器适配器，它们只是对其他容器的接口进行了包装。STL中stack和queue默认使用deque作为底层容器。
4.3 deque的简单介绍
4.3.1 deque的原理介绍
deque（双端队列）是一种双开口的"连续"空间的数据结构：
- 可以在头尾两端进行插入和删除操作，时间复杂度为O(1)
- 与vector比较，头插效率高，不需要搬移元素
- 与list比较，空间利用率比较高
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际类似于一个动态的二维数组。
4.3.2 deque的缺陷
- 不适合遍历，因为迭代器要频繁检测是否移动到小空间边界
- 在实际中，需要线性结构时，大多数情况下优先考虑vector和list
- deque的应用并不多，主要作为stack和queue的底层数据结构
4.4 为什么选择deque作为stack和queue的底层默认容器
- stack和queue不需要遍历（因此没有迭代器），只需要在固定的一端或两端操作
- 在stack中元素增长时，deque比vector的效率高（扩容时不需要搬移大量数据）
- queue中的元素增长时，deque不仅效率高，而且内存使用率高
4.5 容器适配器设计的关键点
从上面的模拟实现可以看出容器适配器的核心设计思想：
- 模板参数灵活性：
- stack和queue都支持自定义底层容器
- priority_queue支持自定义比较器，实现大堆/小堆切换
- 接口统一性：
- 所有适配器都提供push、pop、top/front/back、size、empty等标准接口
- 隐藏底层容器的具体实现细节
- 代码复用：
- 通过组合已有的容器实现新功能
- 减少代码重复，提高开发效率
总结
栈、队列和优先队列是三种基础且重要的数据结构，在C++ STL中通过容器适配器的方式实现。理解它们的底层原理、使用场景和实现方式，对于提高编程能力和解决实际问题都有重要意义。
通过模拟实现这些数据结构，我们可以：
- 深入理解容器适配器设计模式
- 掌握仿函数在泛型编程中的应用
- 理解堆算法的实现原理
- 学会如何设计灵活的、可扩展的数据结构
在实际开发中，根据具体需求选择合适的数据结构：
- 需要后进先出操作时选择栈
- 需要先进先出操作时选择队列
- 需要快速获取最大/最小值时选择优先队列
