【C++】stack、queue和priority_queue的模拟实现

---

前言

之前已经模拟实现了vector和list，在这篇博文中，我们要对stack和queue进行模拟实现。在开始之前，先讲一个东西：容器适配器。

适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

在 C++ 标准库中，容器适配器（Container Adaptors）是一种特殊的容器，它们并非独立的容器类型，而是对现有容器类型进行了封装和适配，以提供特定的接口和行为。容器适配器主要有三种：stack（栈）、queue（队列）和priority_queue（优先队列）。

其中，stack，queue，priority_queue就是通过封装容器deque(双端队列)和vector(动态数组)适配成特定的容器：容器适配器。

这里的容器适配器是设计模式的一种：适配器模式，在此之前，我们学过另外一种设计模式：迭代器模式。

迭代器模式：通过封装底层实现细节，并且提供统一的访问方式来访问容器。
适配器模式：通过封装已有的东西，再提供特定的接口来转换出想要的东西。

一. stack

1.1 stack的介绍

stack的文档介绍

1. 栈是一种容器适配器，其特点是先进后出，只能从容器的一端进行插入和提取元素。
2. 栈是作为容器适配器被实现的，容器适配器是使用特定容器类的封装对象作为其基础容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的尾部(栈顶)被压入和弹出。
3. 底层容器可以是任何标准容器类模板或其他专门设计的容器类。这些容器类应支持以下操作：

empty：判断容器是否为空
size：获取容器的元素个数
back：获取容器的尾部元素
push_back：在容器尾部插入一个元素
pop_back：删除容器尾部元素

4. 标准容器vector、list、deque均符合以上要求。如果没有为stack指定一个底层容器类，则默认情况下使用deque。

1.2 stack的使用

函数说明	接口说明
stack()	构造空的栈
empty()	检测stack是否为空
size()	返回stack中元素的个数
top()	返回栈顶元素的引用
push()	将元素val压入stack中
pop()	将stack中尾部元素弹出

1.3 stack的模拟实现

因为stack是对容器的封装，所以默认构造函数、析构函数、赋值运算符重载函数等都不需要自己手动去实现，编译器自动生成的会调用底层容器(如vector)的默认成员函数。

//防止与std库里的stack冲突
namespace MyStack {//底层容器可以是vector,list,deque，deque兼容了vector和list所有的接口//因为只学习了vector和list，就以vector作为底层容器，即为顺序栈//如果以list作为底层容器，即为链栈//template<class T, class Container = list<T>>template<class T, class Container = vector<T>>class stack{public:stack(){}void push(const T& val){_con.push_back(val);}void pop(){assert(!empty());_con.pop_back();}const T& top() const{return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}void swap(stack& st){_con.swap(st._con);}private:Container _con;};
}

测试：

void Test()
{MyStack::stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);MyStack::stack<int> st1(st);st1.push(5);st1.swap(st);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;while (!st1.empty()){cout << st1.top() << " ";st1.pop();}cout << endl;
}

二. queue

2.1 queue的介绍

queue的文档介绍

总结：

1. 队列是一种容器适配器，其特点为先进先出，其中从容器一端插入元素，另一端提取元素。
2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列

4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

2.2 queue的使用

函数声明	接口说明
queue()	构造空的队列
empty()	检测队列是否为空，是就返回true，否则返回false
size()	返回队列中有效元素的个数
front()	返回队头元素的引用
back()	返回队尾元素的引用
push()	在队尾将元素val入队列
pop()	将队头元素出队列

2.3 queue的模拟实现

与stack一样，我们不需要手动去实现默认成员函数，编译器自动生成的就满足需求了。

//防止与std库里的queue冲突
namespace MyQueue {//底层容器可以是list和deque，这里使用较为熟悉的listtemplate<class T, class Container = list<T>>class queue{public:void push(const T& val){_con.push_back(val);}void pop(){assert(!empty());_con.pop_front();}const T& front() const{assert(!empty());return _con.front();}const T& back() const{assert(!empty());return _con.back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}void swap(queue& q){_con.swap(q._con);}private:Container _con;};
}

注意：不能使用vector作为底层容器，因为vector不支持高效的头部删除操作。

测试：

void Test()
{MyQueue::queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);MyQueue::queue<int> q1(q);q1.push(5);q1.push(6);q.swap(q1);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;while (!q1.empty()){cout << q1.front() << " ";q1.pop();}cout << endl;
}

三. deque

vector和list各有缺点：

vector：1.头部中部插入删除效率低；2.要扩容
list：1.不支持随机访问；2.cpu高速缓存命中率低

那有没有一种完美的容器，可以将两者的优点结合，缺点抹除呢？

答案是有的，这个容器就是deque。下面来了解一下deque。

3.1 deque的原理介绍

deque(双端队列)：是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高，且支持随机访问。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

map数组存储所有的缓冲区，当缓冲区不够用了，就创建新的map数组，将旧的map数组存储的缓冲区地址拷贝给新的map数组，最后将旧的map数组释放掉即可。

双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

那deque是如何借助其迭代器维护其假想连续的结构呢？

迭代器存储四个成员：first（指向当前缓冲区的头部），last（指向当前缓冲区的尾部），cur（指向当前元素的指针），node（指向当前缓冲区地址在中控数组存储的位置）。

deque的随机下标访问：
分为两种情况：

1. 访问的元素在当前缓冲区

直接移动cur指针到指定位置即可。

2. 访问的元素不在当前缓冲区。

因为buffer数组的大小是固定的，所以我们可以先用下标/buffer数组的大小，找到要访问的元素在第几个buffer数组里；再根据下标%buffer数组的大小，得到要访问的元素在buffer数组的第几个位置。

deque的随机下标访问还是挺麻烦的，也没有vector快，虽然兼容了vector和list，但是它的优点也不突出。

3.2 deque的缺陷

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

deque的使用场景：

1、中部插入删除操作少，头尾插入删除操作多
2、偶尔进行随机下标访问

3.3 为什么选择deque作为stack和queue的底层默认容器

stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。但是STL中对stack和queue默认选择deque作为其底层容器，主要是因为：

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，queue不仅效率高，而且内存使用率高。

结合了deque的优点，而完美的避开了其缺陷。

感兴趣的可以看一下deque的模拟实现：
c++编程(17)——deque的模拟实现（1）迭代器篇
c++编程（18）——deque的模拟实现（2）容器篇
deque的模拟实现源代码

四. priority_queue（优先队列）

4.1 priority_queue的介绍

priority_queue的文档介绍

总结：

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的"尾部"弹出，其称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

4.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

函数声明	接口说明
priority_queue()/priority_queue(first,last)	构造一个空的优先级队列
empty()	检测优先级队列是否为空，是返回true，否则返回false
top()	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

1. 存储的是内置类型

void Test()
{//默认情况下，创建的是大堆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;//如果要创建小堆，将第三个模板参数换成greater比较方式priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());cout << q2.top() << endl;
}

2. 如果在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);}friend ostream& operator<<(ostream& _cout, const Date& d);
private:int _year;int _month;int _day;
};
ostream& operator<<(ostream& _cout, const Date& d)
{_cout << d._year << "-" << d._month << "-" << d._day;return _cout;
}
void Test()
{// 大堆，需要用户在自定义类型中提供<的重载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;
}

4.3 priority_queue的模拟实现

因为priority_queue的底层结构就是堆，因此我们只需对其进行封装即可。

如果对堆不熟悉的可以看这篇博客：数据结构：二叉树(堆)的顺序存储

4.3.1 向上调整算法

作用：向上调整当前结点，使其满足堆结构。
主要应用：插入一个结点时(在堆尾)，最后一个结点向上调整满足堆结构。

void AdJustUp(int child)
{int parent = (child - 1) / 2;if (parent >= 0 && _con[parent]<_con[child]) {std::swap(_con[parent], _con[child]);AdJustUp(parent);}
}

4.3.2 向下调整算法

作用：向下调整当前结点，使其满足堆结构。
主要应用：1. 向下调整算法建堆；2.删除堆顶结点时，第一个结点(堆顶)与最后一个结点(堆底)交换，将最后一个结点删除后，让第一个结点(堆顶)向下调整满足堆结构。

void AdjustDown(int parent)
{int child = 2 * parent + 1;if (child + 1 < _con.size() && _con[child]<_con[child + 1]) {child++;}if (child < _con.size() && _con[parent]<_con[child]) {std::swap(_con[child], _con[parent]);AdjustDown(child);}
}

4.3.3 整体代码

namespace Mypriority_queue {template<class T, class Container = vector<T>>class priority_queue{public://强制生成默认构造priority_queue() = default;template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//使用向下调整算法建堆for (int i = (_con.size() - 2) / 2; i >= 0; i--){AdjustDown(i);}}void AdJustUp(int child){int parent = (child - 1) / 2;if (parent >= 0 && _con[parent]<_con[child]) {std::swap(_con[parent], _con[child]);AdJustUp(parent);}}void push(const T& val){_con.push_back(val);AdJustUp(_con.size() - 1);}void AdjustDown(int parent){int child = 2 * parent + 1;if (child + 1 < _con.size() && _con[child]<_con[child + 1]) {child++;}if (child < _con.size() && _con[parent]<_con[child]) {std::swap(_con[child], _con[parent]);AdjustDown(child);}}void pop(){assert(!empty());std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top() const{assert(!empty());return _con[0];}bool empty() const{return _con.empty();}bool size() const{return _con.size();}void swap(priority_queue& q){_con.swap(q._con);}private:Container _con;};
}

为什么使用向下调整算法建堆？

因为向下调整算法建堆的时间复杂度为O(N)，向上调整算法建堆的时间复杂度为O(NlogN)，优先用时间复杂度低的。

注意：向下调整算法建堆要从最后一个结点的父节点开始，依次到根节点后结束。

整体已经实现的差不多了，还有最后一个：仿函数，接下来我们来看一下仿函数是如何实现大小堆的。

五. 仿函数

仿函数实际上就是一个类，通过重载operator()，可以让我们像使用函数一样去使用这个类。

namespace GL
{template<class T>struct less {bool operator()(const T& left, const T& right) const{return left < right;}};template<class T>struct greater {bool operator()(const T& left, const T& right) const{return left > right;}};
}
void Test()
{GL::greater<int> g;cout << g(2, 3) << endl;GL::less<int> l;cout << l(2, 3) << endl;
}

less是判断第一个参数是否小于第二个参数，greater是判断第一个参数是否大于第二个参数。

通过对仿函数的了解，我们知道了priority_queue的第三个模板参数就是用来控制大小堆的（默认为less，就是大堆，如果传的是greater，就是小堆）。

namespace Mypriority_queue {template<class T>struct less {bool operator()(const T& left, const T& right) const{return left < right;}};template<class T>struct greater {bool operator()(const T& left, const T& right) const{return left > right;}};template<class T, class Container = vector<T>,class Compare = less<T>>class priority_queue{public://强制生成默认构造priority_queue() = default;template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last){//使用向下调整算法建堆for (int i = (_con.size() - 2) / 2; i >= 0; i--){AdjustDown(i);}}void AdJustUp(int child){int parent = (child - 1) / 2;if (parent >= 0 && Compare()(_con[parent],_con[child])) {std::swap(_con[parent], _con[child]);AdJustUp(parent);}}void push(const T& val){_con.push_back(val);AdJustUp(_con.size() - 1);}void AdjustDown(int parent){int child = 2 * parent + 1;if (child + 1 < _con.size() && Compare()(_con[child],_con[child + 1])) {child++;}if (child < _con.size() && Compare()(_con[parent],_con[child])) {std::swap(_con[child], _con[parent]);AdjustDown(child);}}void pop(){assert(!empty());std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}const T& top() const{assert(!empty());return _con[0];}bool empty() const{return _con.empty();}bool size() const{return _con.size();}void swap(priority_queue& q){_con.swap(q._con);}private:Container _con;};
}

测试：

void Test()
{vector<int> v = { 2,3,1,4,7,6,5 };Mypriority_queue::priority_queue<int> q1(v.begin(), v.end());while (!q1.empty()){cout << q1.top() << " ";q1.pop();}cout << endl;Mypriority_queue::priority_queue<int, vector<int>, Mypriority_queue::greater<int>> q2(v.begin(), v.end());while (!q2.empty()){cout << q2.top() << " ";q2.pop();}cout << endl;
}

再来看一下以下这段代码：

void Test()
{Mypriority_queue::priority_queue<Date*> q;q.push(new Date(2025, 1, 1));q.push(new Date(2025, 2, 1));q.push(new Date(2025, 3, 1));while (!q.empty()){cout << *q.top() << " ";q.pop();}cout << endl;
}

为什么两次运行的结果是不一样的，还是错误的呢？

因为存储的类型为指针类型Date*，而仿函数默认比较的就是Date*，因为地址是随机性的，而堆顶是地址值最大的Date对象，所以每次运行的结果都不一样。

解决办法就是自己再写一个专门用于比较Date*的仿函数：

struct Less
{bool operator()(const Date* d1, const Date* d2){return *d1 < *d2;}
};
struct Greater
{bool operator()(const Date* d1, const Date* d2){return *d1 > *d2;}
};
void Test()
{Mypriority_queue::priority_queue<Date*, vector<Date*>, Less> q;q.push(new Date(2025, 1, 1));q.push(new Date(2025, 2, 1));q.push(new Date(2025, 3, 1));while (!q.empty()){cout << *q.top() << " ";q.pop();}cout << endl;Mypriority_queue::priority_queue<Date*, vector<Date*>, Greater> q1;q1.push(new Date(2025, 1, 1));q1.push(new Date(2025, 2, 1));q1.push(new Date(2025, 3, 1));while (!q1.empty()){cout << *q1.top() << " ";q1.pop();}cout << endl;
}

最后

stack、queue、priority_queue的模拟实现到这里就结束了，对以上内容有异议或者需要补充的，欢迎大家来讨论！

本文整体代码：stack,queue,priority_queue的模拟实现