【stack】【queue】【priority_queue】【deque】详解

利刃大大

发布于 2023-04-12 14:19:20

1.2K0

文章被收录于专栏：csdn文章搬运csdn文章搬运

Ⅰ. stack的介绍和使用

1.stack的概念

🔍 文档介绍：stack - C++ Reference

stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认情况下使deque（双向队列）。

stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
- empty： 判空操作
- back： 获取尾部元素操作
- push_back： 尾部插入元素操作
- pop_back： 尾部删除元素操作

通过观察文档我们不难发现，接口相较于之前的 string、vector 和 list 少了很多。它甚至连拷贝构造和析构都没有自己实现，然而这些都得益于容器适配器的使用。

不难发现， stack、queue 也没有迭代器，这也不难理解，因为栈和丢列本来不是用来遍历的，这样子的话只会破坏他们的原则。

2.stack的使用

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

测试代码：

#include <iostream>
#include <stack>
using namespace std;
 
void test_stack() {
    /* 创建一个存储整型的栈 */
    stack<int> st;
 
    /* 入栈 */
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
 
    /* 打印栈 */
    while (!st.empty()) {           // 如果栈不为空则进入循环
        cout << st.top() << " ";    // 打印栈顶元素
        st.pop();                   // 出栈
    }
    cout << endl;
}

🚩 运行结果：4 3 2 1

Ⅱ.queue的介绍和使用

1.queue的概念

队列只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

入队列，进行插入操作的一端称为队尾。出队列，进行删除操作的一端称为队头。

队列中的元素遵循先进先出的原则，即 FIFO 原则（First In First Out）。

🔍 文档介绍：queue - C++ Reference

队列是一种容器适配器，专门用于在FIFO上下文**(先进先出)**中操作，其中从容器一端插入元素，另一端提取元素。
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque（双向队列）。
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：
- empty： 检测队列是否为空
- size： 返回队列中有效元素的个数
- front： 返回队头元素的引用
- back： 返回队尾元素的引用
- push_back： 在队列尾部入队列
- pop_front： 在队列头部出队列

2.queue的使用

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

💬 代码演示： queue

#include <iostream>
#include <queue>
using namespace std;
 
void test_queue() {
    /* 创建一个存储整型的队列 */
    queue<int> Q;
 
    /* 入队 */
    Q.push(1);
    Q.push(2);
    Q.push(3);
    Q.push(4);
 
    /* 打印队列 */
    while (!Q.empty()) {             // 如果队列不为空则进入循环
        cout << Q.front() << " ";    // 打印队头元素
        Q.pop();                     // 出队
    }
    cout << endl;
}

🚩 运行结果：4 3 2 1

Ⅲ.priority_queue（优先级队列）的介绍和使用

1.优先级队列的概念

🔍 文档介绍：priority_queue - C++ Reference

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()： 检测容器是否为空
- size()： 返回容器中有效元素个数
- front()： 返回容器中第一个元素的引用
- push_back()： 在容器尾部插入元素
- pop_back()： 删除容器尾部的元素
标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用vector 。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2.优先级队列的使用

从上面的概念可以看出，优先级队列就是一个堆，而且默认是个大堆！

优先级队列默认使用 vector 作为其底层存储数据的容器，

在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因为 priority_queue 就是堆。

所有需要用到堆的地方，都可以考虑使用 priority_queue。

优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆；

如果想控制小的优先级高，需手动传 greater 仿函数，其底层是一个小堆。

可能是因为大堆是默认从大到小递减，所以才讲仿函数名称设为 less 哈哈。

（仿函数我们下面在实现的时候会具体讲）

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

🌵 优先级队列的定义:

priority_queue<int> qe;
		👇（默认情况下）		
priority_queue<int, vector<int>, less<int>> qe;

//若将适配器容器改为list
priority_queue<int, list<int>, less<int>> qe;

注：若需要修改仿函数，则不可越过模板的第二个参数 Container 去直接设置仿函数，因为模板无法这样子自动识别你想修改的参数是第二个还是第三个，所以要将第二个参数也传过去（下面是定义，仔细观察缺省值部分）

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

如下就是错误示范：

priority_queue<int, greater<int>>   ❌  //没有传第二个参数！

默认情况下，priority_queue是大堆。

💬 代码演示：

#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
     // 默认情况下，创建的是大堆，其底层按照小于号比较
     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;
}

🚩 运行结果：9  0

🔑 解读： 默认是用 vector 存储的，注意这里没有明确指定 less 还是 greater，所以默认为 less。

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

🚩 运行结果:
2018-10-30
2018-10-28

Ⅳ.deque（双端队列）

1.deque（double-ended-queue）的原理介绍

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

它提供了和 vector 类似的接口但是底层的实现和 vector 却完全不同，最大的区别在于 vector 的所有元素都是连续的，但是 deque 不全是！因为 deque 也像 list 一样，按需申请空间，但是和 list 不一样的是，deque 申请的空间不只是一个空间的大小，而是多个，按结构上来说，就像是一个动态的二维数组！ deque在底层实现上是将一个连续的空间 分段进行管理，并将它们的首地址用一个 指针数组 进行管理，这样特殊的存储结构使得它在头部和尾部增加元素比vector更加高效，但是底层实现更为复杂，存储了很多额外信息。如果抛去在头部和尾部增加元素，在中间任意位置添加元素，它的效率比 vector 更高，但是比 list 要低。功能上其实是 vector 和 list 的结合！

❓ 问题： deque 看起来这么牛逼，那能不能用它代替我们的 vector 和 list 呢！

💡 解答： 肯定不行！因为 deque 比较适合头尾插入删除，但是不太适合大量的中间插入删除以及大量的随机访问，效率不如单单的使用 list 和 vector 那么高。实际中 deque 作为线性表结构，一般作为 stack 和 queue 的默认适配容器。所以 deque 是很难替代 vector 和 list 的！只是说 deque 具有两者的功能而已！

2.deque 的常用接口

构造函数

deque();                                                  //构造空的双端队列
deque(size_type n, const value_type& val = value_type()); //用n个值为val的元素构造双端队列
deque(InputIterator first, InputIterator last);           //用[first, last)的区间构造双端队列
deque(const deque &x);                                    //双端队列的拷贝构造函数

迭代器相关

iterator begin();                       //返回deque起始位置迭代器
iterator end();                         //返回deque最后一个元素下一个位置的迭代器
reverse_iterator rbegin();              //返回deque起始位置的反向迭代器(即end())
reverse_iterator rend();                //返回deque最后一个元素下一个位置的反向迭代器(begin())

const_iterator cbegin() const;          //返回deque起始位置的const迭代器
const_iterator cend() const;            //返回deque最后一个元素下一个位置的const迭代器
const_reverse_iterator crbegin() const; //返回deque起始位置的const反向迭代器(即crend())
const_reverse_iterator crend() const;   //返回deque最后一个元素下一个位置的const反向迭代器(crbegin())

容量相关

size_type size() const;                           //返回deque中有效元素个数
bool empty() const;                               //检测deque是否为空，是返回true，否则返回false
void resize (size_type n, const T& val = T());    //将deque中的元素改变到sz，多出的空间用val填充

增删查改

reference operator[](size_type n);                         //返回deque中n位置上元素的引用
reference front();                                         //返回deque中首元素的引用
reference back();                                          //返回deque中最后一个元素的引用

void push_back(const value_type &val);                     //deque尾部插入元素val
void pop_back();                                           //删除deque尾部元素
void push_front(const value_type &val);                    //deque头部插入元素val
void pop_front();                                          //删除deque头部元素

//在deque的position位置插入值为val的元素
iterator insert(iterator position, const value_type &val); 
//在deque的position位置插入n个值为val的元素
void insert(iterator position, size_type n,const value_type &val);
//在deque的position位置插入[first, last)区间中的元素
void insert(iterator position, InputIterator first, InputIterator last); 
//删除deque中position位置的元素，并返回该位置的下一个位置
iterator erase(iterator position);                                       
//删除deque中[first, last)区间中的元素，并返回last位置
iterator erase(iterator first, iterator last);         
//交换两个deque中的内容
void swap(deque & x);          
//将deque中的元素清空
void clear();             

//在deque的position位置构造元素，将元素所需内容通过参数类表传入
iterator emplace(const_iterator position, Args && ... args);             
void emplace_front(Args && ... args);          //在deque的头部构造元素，元素的参数通过参数列表传入
void emplace_back(Args && ... args);           //在deque的尾部构造元素，元素的参数通过参数列表传入

测试代码：

void testDeque()
{
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_back(2);

    deque<int>::iterator it = dq.begin();
    while (it != dq.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    it = dq.erase(--it);
    it = dq.begin();
    while (it != dq.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

🚩 运行结果:
1 2 3 2
1 2 3

3.deque 的实现原理

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其 “整体连续” 以及随机访问的假象，落在了 deque的迭代器身上，因此deque的迭代器设计就比较复杂，
那 deque 是如何借助其迭代器维护其假想连续的结构呢？

由于deque在内存上并不完全是连续的因此想要保持 deque 的连续性，这个任务就落到了迭代器身上。在底层实现上，deque将一段一段连续的内存称为一个 缓冲区(buffer)，并将这些缓冲区的首尾地址存储在一个 map 中用以映射，map 中一个存储缓冲区的地址对应一个 结点(node) 信息用于标记这个键值对，这样就构建好了基础架构。在迭代器中存储了4个信息，分别是当前结点(cur)，当前缓冲区的头(first)，当前缓冲区的尾(last) 以及在 map 中用以标记当前缓冲区的地址的 结点(node) 信息。并且在deque内部已经存储好了两个迭代器start和finish用于标记deque的头和尾元素。这样即可完成将一段一段连续的空间在逻辑结构上构成一段连续空间的目的。当从头遍历deque时，start迭代器中first和last已经从 map 中找到了第一个结点的缓冲区首尾信息并进行了保存，于是cur就从first开始遍历这个缓冲区，当遍历到last时就重新到 map 中寻找写一个结点的缓冲区收尾地址并且替换掉原来first和last值，继续遍历，这样即可完成遍历直到最后一个结点也遍历完。

总结

双端队列deque是一个设计并不算成功的容器，如果要随机访问单纯的查询多一点可以用vector而且更加方便，如果需要频繁插入那么list效率又会跟高，因此deque并不常用，其最常用的地方就是在作为适配器stack和queue的底层存储容器。

4.deque的缺陷

deque 有点像 vector 和 list 的结合体，我们把 vector 和 list 也拉出来进行优缺点的对比再合适不过了：

容器	优点	缺点
vector	适合尾插尾删，随机访问	① 不适合头部或者中部的插入删除，效率低下，需要挪动数据。② 扩容有一定程度的性能消耗，还可能存在一定程度的空间浪费。
list	① 适合任意位置的插入删除，效率高，O(1)时间复杂度 ② 按需申请空间，空间利用率比较高	① 不支持随机访问 ② CPU 高速缓存命中率低
deque	① 头部和尾部插入数据效率不错 ② 支持随机访问 ③ 扩容代价小 ④CPU高速缓存命中高	① 中部的插入删除效率不行② 不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，③ 不够极致。

❓ 那什么场景适合用 deque 呢？

虽然不够极致但是还是有用武之地的：大量头尾插入删除，偶尔随机访问的情况可以使用 deque。

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

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

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

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

Ⅴ.容器适配器

在模拟实现 stack 和 queue 和 priority_queue，我们得重新来回顾一下容器适配器，也可以参考 list 笔记中的解释。

什么是适配器 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
STL标准库中stack和queue的底层结构虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，比如：

也就是说，容器适配器就是将已经存在的容器（如vector）拿过来实现适配器，达到复用的效果！

Ⅵ. stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的 vector，因此使用 vector 完全可以模拟实现 stack。

但是为了和 STL 中的接口保持一致：STL 增加了一个模板参数 Container，利用 Container 来进行转换，而 STL 中还用 deque 去作为默认的适配器实现 stack，所以我们这里就统一使用 deque 作为默认适配器！

❓ 思考： 可否用 string 作为适配器？勉强可以，只要你是顺序容器都可以。但是用 string 是有风险的，可能会出现溢出和截断。

#pragma once
#include<iostream>
#include<deque>
using std::deque; //记得要引入std中的deque

namespace liren
{
    //可以任意设置容器适配器，只要满足接口功能要求即可
    //template<class T, class Container = vector<int>>
    //template<class T, class Container = list<int>>
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& val) // 对于栈而言，入栈就是尾插
		{
			_con.push_back(val);
		}

		void pop() // 对于栈而言，出栈就是尾删
		{
			_con.pop_back();
		}

		T& top() // 返回尾上数据
		{
			return _con.back();
		}
		const T& top() const //const版本
		{
			return _con.back();
		}

		size_t size() const // 返回栈大小
		{
			return _con.size();
		}

		bool empty() const // 返回栈是否为空
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}

测试代码：

void Testmystack()
{
    liren::stack<int> st;
    st.push(1);
    st.push(4);
    st.push(3);
    st.push(2);
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;

    //也可以传不同的适配器，照样能跑
    liren::stack<int, vector<int>> s;
    s.push(1);
    s.push(4);
    s.push(3);
    s.push(2);
    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

🔺 总结： 从上层角度来看，其默认是一个双端队列，我底层用什么存，去实现这个栈并不重要，只要其符合要求就行。它保存的是栈的性质，复用的是容器的代码。

Ⅶ.queue的模拟实现

同样，queue 也用 deque 来作为默认容器实现，与 stack 的代码基本没什么变化！

queue 是先进先出的，queue 的 push 仍然是尾部的插入，而 pop 需要支持头部的删除！

值得注意的是，queue 不能用 vector 去适配，因为 vector 压根就没有 pop_front() 等接口。

#pragma once
#include<iostream>
#include<deque>
using std::deque;  //同样也要引入std中的deque

namespace liren
{
	template<class T, class Container = deque<int>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& back()
		{
			return _con.back();
		}
		const T& back() const
		{
			return _con.back();
		}

		T& front()
		{
			return _con.front();
		}
		const T& front() const
		{
			return _con.front();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

测试代码：

void Testmyqueue()
{
    liren::queue<int> q;
    q.push(1);
    q.push(3);
    q.push(4);
    q.push(2);
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    //✔也可以传list容器，照样能跑
    liren::queue<int, list<int>> q1;
    q1.push(1);
    q1.push(3);
    q1.push(4);
    q1.push(2);
    while (!q1.empty())
    {
        cout << q1.front() << " ";
        q1.pop();
    }
    cout << endl;

    //❌这是跑不过的，因为vector不支持pop_front()等函数
    liren::queue<int, vector<int>> q2;
    q2.push(1);
    q2.push(1);
    q2.push(1);
    q2.push(1);
    while (!q2.empty())
    {
        cout << q2.front() << " ";
        q2.pop();
    }
    cout << endl;
}

Ⅷ.priority_queue的模拟实现

1.仿函数（functor）（用库里的需引入头文件<functional>）

在模拟实现优先级队列之前，我们得先来了解一个概念，那就是仿函数！

❓ 问题： 为什么实现 priority_queue 要了解仿函数？ 💡 解答： 其实 priority_queue 本质就是一个堆，而且默认是个大堆！也就是说 priority_queue 第一个元素是最大的。那如果我们需要的是个小堆呢？那该怎么办？所以这个时候我们就得传仿函数给模板当参数，让模板来控制我们想要的。

📚 概念： 使一个类的使用看上去像一个函数。可以像函数一样使用的对象，称为函数对象。

其实现就是在类中重载 operator()，使得该类具备类似函数的行为，就是一个仿函数类了。

C语言优先级，() 圆括号使用形式为 表达式或 “作为函数形参列表的括号” 我们这里重载的其实就是：函数名(形参表)

👁‍🗨 比如下面的代码就是比较 重载的() 与函数的区别:

//仿函数 -- 函数对象（可以像函数一样去使用）
struct lessInt
{
    bool operator()(int left, int right)
    {
        return left < right;
    }
};

//函数的正常形式
bool lessFunc(int left, int right)
{
    return left < right;
}

void testFunctor()
{
    //仿函数的使用
    lessInt less;
    cout << less(1, 2) << endl;

    //正常函数的使用
    cout << lessFunc(1, 2) << endl;
}

🚩 运行结果:
1
1

❓ 思考：我们在C阶段不是学过函数指针么，用函数指针不香吗？

函数指针确实可以做到这些功能。但是在这里函数指针跟仿函数比，一点都不香！ 函数的指针在一些地方用起来非常复杂。

比如下面的代码：

static void( * set_malloc_handler(void (*f)()))() 
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}

这个函数的参数是什么？函数的返回值是什么？

这就很阴间了，这就是函数指针的杰作…… 所以 C++ 搞出了仿函数，简化了好多。

📚 仿函数的优势： 很多场景，替换了函数指针。

2.优先级队列的实现思路

priority_queue 的底层结构就是堆，因此只需对堆进行通用的封装即可。

默认情况下的优先级队列是大堆，那么如果我们像让其变成小堆，则要我们另行传仿函数，这个只需要我们构造即可。

对于主体框架

有了仿函数的了解之后，我们就可以控制大小堆的问题啦！那我们先把 priority_queue 的主体结构搭建起来，因为 priority_queue 本质是堆，所以我们用 vector 来作为其默认的容器适配器！

#pragma once
#include<iostream>
#include<vector>
using std::vector;

namespace liren
{
    //这里的Compare就是我们的仿函数！
	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
    public:
        // 创造空的优先级队列
		priority_queue() : _con() 
		{}

	private:
		Container _con;
	};
}

对于常规接口

与 stack 和 queue 一样，优先级队列的几个接口也是一样的实现方法，如 size()，empty() 和 top()，所以我们先将其实现！

size_t size() const
{
	return _con.size();
}

// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
const T& top() const
{
	return _con.front();
}

bool empty() const
{
	return _con.empty();
}

对于仿函数

可以从上面的框架代码看到，对于大堆，STL 中默认的取名叫做 less，而对于小堆，我们要取名为 greater ！

❓ 是不是觉得很奇怪，为什么大堆反而取名为 less 呢？ 💡 解答： 以我的理解，大堆是降序的，是依次变小的，所以用 less，其实也是合理的，而 greater 则反之！

📡 代码如下：

//less是用来比较谁小的
template<class T>
    struct less
    {
        bool operator()(const T& left, const T& right)
        {
            return left < right;
        }
    };

//greater是用来比较谁大的
template<class T>
    struct greater
    {
        bool operator()(const T& left, const T& right)
        {
            return left > right;
        }
    };

对于向上和向下调整算法

因为 priority_queue 是个堆，所以我们等会实现插入删除的时候是需要重新调整堆的大小顺序的，所以我们先将其调整算法写出来！

💃 注意一个点，就是这种调整算法是不太允许被外面的其他接口随便调的，所以我们要将其设为 private。 💃 还有一个点，就是向上调整算法中，parent 和 child 最好不要将其类型设为 size_t ，因为可能会出现小于0的情况。

这个知识点并不难，只要还是堆的知识，所以这里直接将代码写出来：

private:
		//向下调整算法
		void AdjustDown(int parent)
		{
			Compare Com;

			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && Com(_con[child], _con[child + 1]))
				{
					child += 1;
				}

				if (Com(_con[parent], _con[child]))
				{
					::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		//向下调整算法
		void AdjustUp(int child)
		{
			Compare Com;

			int parent = (child - 1) >> 1;
			while (child > 0)
			{
				if (Com(_con[parent], _con[child]))
				{
					::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) >> 1;
				}
				else
					break;
			}
		}

对于尾插头删

优先级队列相较于普通的队列，其区别主要是在 push 和 pop 上，

即需要在插入 / 删除数据的同时，增添调整的功能，并且 STL 的优先级队列是由堆来维护的：

入队时将数据推入后，从最后一个元素开始进行上调。 出队时采用堆的删除手法，将根元素（即队头）和最后一个元素进行交换，并调用尾删掉队头。既然用了头尾交换法，我们就不得不对队列重新调整，所以从根位置进行下调，即可完成出队。

void push(const T& val)
{
    _con.push_back(val);
    AdjustUp(_con.size() - 1);
}

void pop()
{
    if (empty())
        return;

    ::swap(_con.front(), _con.back()); //多调用容器的接口复用
    _con.pop_back();
    AdjustDown(0);
}

迭代器构造函数的实现

对于优先级队列，我们直接用 vector 的构造函数来完成迭代器构造函数即可！

最主要的问题是，用 vector 的迭代器区间来构造 vector 后，我们要对其进行建堆，让其变成一个名副其实的优先级队列！

template<iterator>
priority_queue(iterator first, iterator last)
: _con(first, last)  //这里其实就调用了vector的构造函数完成了构造
{
    // 将_con中的元素调整成堆的结构
    for (int parent = (_con.size() - 1 - 1) >> 1; parent >= 0; parent--)
    {
        AdjustDown(parent);
    }
}

3.测试代码：

void testMypriority_queue()
{
    liren::priority_queue<int> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    pq.push(4);
    pq.push(5);
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    //也可以将其改为小堆顺序
    liren::priority_queue<int, vector<int>, liren::greater<int>> pq2;
    pq2.push(1);
    pq2.push(2);
    pq2.push(3);
    pq2.push(4);
    pq2.push(5);
    while (!pq2.empty())
    {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << endl;

    //还可用迭代器构造区间
    vector<int> v{ 5,1,4,2,3,6 };
    liren::priority_queue<int, vector<int>, liren::greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;

    q2.pop();
    q2.pop();
    cout << q2.top() << endl;
}

Ⅸ.完整代码

1. stack.h

#pragma once
#include<iostream>
#include<deque>
using std::deque; //记得要引入std中的deque

namespace liren
{
	template<class T, class Container = deque<T>>
	class stack
	{
	public:
		void push(const T& val) // 对于栈而言，入栈就是尾插
		{
			_con.push_back(val);
		}

		void pop() // 对于栈而言，出栈就是尾删
		{
			_con.pop_back();
		}

		T& top() // 返回尾上数据
		{
			return _con.back();
		}
		const T& top() const //const版本
		{
			return _con.back();
		}

		size_t size() const // 返回栈大小
		{
			return _con.size();
		}

		bool empty() const // 返回栈是否为空
		{
			return _con.empty();
		}

	private:
		Container _con;
	};
}

2. queue.h

#pragma once
#include<iostream>
#include<deque>
using std::deque;  //同样也要引入std中的deque

namespace liren
{
	template<class T, class Container = deque<int>>
	class queue
	{
	public:
		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& back()
		{
			return _con.back();
		}
		const T& back() const
		{
			return _con.back();
		}

		T& front()
		{
			return _con.front();
		}
		const T& front() const
		{
			return _con.front();
		}

		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con;
	};
}

3. priority_queue.h

#pragma once
#include<iostream>
#include<vector>
using std::vector;

namespace liren
{
	//less是用来比较谁小的
	template<class T>
	struct less
	{
		bool operator()(const T& left, const T& right) const
		{
			return left < right;
		}
	};

	//greater是用来比较谁大的
	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right) const
		{
			return left > right;
		}
	};

	//这里的Compare就是我们的仿函数！
	template<class T, class Container = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		// 创造空的优先级队列
		priority_queue() : _con() 
		{}

		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: _con(first, last)  //这里其实就调用了vector的构造函数完成了构造
		{
			// 将_con中的元素调整成堆的结构
			for (int parent = (_con.size() - 1 - 1) >> 1; parent >= 0; parent--)
			{
				AdjustDown(parent);
			}
		}

		void push(const T& val)
		{
			_con.push_back(val);
			AdjustUp(_con.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;

			::swap(_con.front(), _con.back()); //多调用容器的接口复用
			_con.pop_back();
			AdjustDown(0);
		}

		size_t size() const
		{
			return _con.size();
		}

		// 堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性
		const T& top() const
		{
			return _con.front();
		}

		bool empty() const
		{
			return _con.empty();
		}

	private:

		//向下调整算法
		void AdjustDown(int parent)
		{
			Compare Com;

			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && Com(_con[child], _con[child + 1]))
				{
					child += 1;
				}

				if (Com(_con[parent], _con[child]))
				{
					::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		//向下调整算法
		void AdjustUp(int child)
		{
			Compare Com;

			int parent = (child - 1) >> 1;
			while (child > 0)
			{
				if (Com(_con[parent], _con[child]))
				{
					::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) >> 1;
				}
				else
					break;
			}
		}

	private:
		Container _con;
	};
}

4. test.cpp

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <queue>
#include<list>
#include <functional> // greater算法的头文件
#include<deque>
#include "stack.h"
#include "queue.h"
#include "priority_queue.h"
using namespace std;

void test_queue() {
    /* 创建一个存储整型的队列 */
    queue<int> Q;

    /* 入队 */
    Q.push(1);
    Q.push(2);
    Q.push(3);
    Q.push(4);

    /* 打印队列 */
    while (!Q.empty()) {             // 如果队列不为空则进入循环
        cout << Q.front() << " ";    // 打印队头元素
        Q.pop();                     // 出队
    }
    cout << endl;
}
void TestPriorityQueue()
{
	// 默认情况下，创建的是大堆，其底层按照小于号比较
	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;
}

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 TestPriorityQueue2()
{
    // 大堆，需要用户在自定义类型中提供<的重载
    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;
}

void testDeque()
{
    deque<int> dq;
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);
    dq.push_back(2);

    deque<int>::iterator it = dq.begin();
    while (it != dq.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    it = dq.erase(--it);
    it = dq.begin();
    while (it != dq.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void Testmystack()
{
    liren::stack<int> st;
    st.push(1);
    st.push(4);
    st.push(3);
    st.push(2);
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;

    //也可以传不同的适配器，照样能跑
    liren::stack<int, vector<int>> s;
    s.push(1);
    s.push(4);
    s.push(3);
    s.push(2);
    while (!s.empty())
    {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

void Testmyqueue()
{
    liren::queue<int> q;
    q.push(1);
    q.push(3);
    q.push(4);
    q.push(2);
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;

    //也可以传list容器，照样能跑
    liren::queue<int, list<int>> q1;
    q1.push(1);
    q1.push(3);
    q1.push(4);
    q1.push(2);
    while (!q1.empty())
    {
        cout << q1.front() << " ";
        q1.pop();
    }
    cout << endl;

    /*liren::queue<int, vector<int>> q2;
    q2.push(1);
    q2.push(1);
    q2.push(1);
    q2.push(1);
    while (!q2.empty())
    {
        cout << q2.front() << " ";
        q2.pop();
    }
    cout << endl;*/
}

//仿函数 -- 函数对象（可以像函数一样去使用）
struct lessInt
{
    bool operator()(int left, int right)
    {
        return left < right;
    }
};

//函数的正常形式
bool lessFunc(int left, int right)
{
    return left < right;
}

void testFunctor()
{
    //仿函数的使用
    lessInt less;
    cout << less(1, 2) << endl;

    //正常函数的使用
    cout << lessFunc(1, 2) << endl;
}

void testMypriority_queue()
{
    liren::priority_queue<int> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    pq.push(4);
    pq.push(5);
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    //也可以将其改为小堆顺序
    liren::priority_queue<int, vector<int>, liren::greater<int>> pq2;
    pq2.push(1);
    pq2.push(2);
    pq2.push(3);
    pq2.push(4);
    pq2.push(5);
    while (!pq2.empty())
    {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << endl;

    //还可用迭代器构造区间
    vector<int> v{ 5,1,4,2,3,6 };
    liren::priority_queue<int, vector<int>, liren::greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;

    q2.pop();
    q2.pop();
    cout << q2.top() << endl;
}

int main()
{
    //test_queue();
    //TestPriorityQueue2();
    //testDeque();
    //Testmyqueue();
    //testFunctor();
    testMypriority_queue();
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-12-21，如有侵权请联系 cloudcommunity@tencent.com 删除

容器