【C++STL精讲】优先级队列（priority_queue）与双端队列（deque)

news/2024/4/30 3:12:29/文章来源:https://blog.csdn.net/gllll_yu/article/details/130274625

在这里插入图片描述

文章目录

💐专栏导读
💐文章导读
🌷优先级队列——priority_queue
- 🌸什么是优先级队列？
- 🌸优先级队列的基本使用
- 🌸什么是仿函数？
- 🌸优先级队列的模拟实现
🌷双端队列——deque
- 🌸deque的优点与缺点
- 🌸deque的原理

💐专栏导读

🌸作者简介：花想云，在读本科生一枚，致力于 C/C++、Linux 学习。

🌸本文收录于 C++系列，本专栏主要内容为 C++ 初阶、C++ 进阶、STL 详解等，专为大学生打造全套 C++ 学习教程，持续更新！

🌸相关专栏推荐：C语言初阶系列 、C语言进阶系列 、数据结构与算法

💐文章导读

本章我们将继续认识一种新的容器适配器——优先级队列（priority_queue）与容器——双端队列（deque）。本文将介绍什么是优先级队列以及优先级队列的基本使用与模拟实现，以及通过list与vector的对比去学习deque。
在这里插入图片描述

🌷优先级队列——priority_queue

🌸什么是优先级队列？

priority_queue与stack和queue相同，都是一种容器适配器。如果你有一定的数据结构基础，或者是曾经阅读过我的数据结构专栏，那么优先级队列就并不是一个什么高大上的东西，它其实就是我之前讲过的——堆。

优先级队列允许你以任意顺序插入元素，并且每次弹出的元素是当前优先级最高（及最大或最小）的元素。在priority_queue中，元素的插入顺序不影响元素的优先级，而是根据其优先级属性进行排序。

🌸优先级队列的基本使用

🍁包含头文件 < queue >;

#include <queue>

🍁定义一个priority_queue对象；

	priority_queue<int> pq;

🍁向队列中插入一个元素；

	pq.push(1);pq.push(5);pq.push(2);

🍁从队列中弹出一个元素（该元素为队列内优先级最高的元素）；

	pq.pop();

🍁返回队列中优先级最高的元素（及堆顶的元素）；

	cout << pq.top() << endl;

🍁返回队列中的元素数量；

	cout << pq.size() << endl;

🍁判断队列是否为空；

	//empty()if (pq.empty()){cout << "Queue is empty" << endl;}else{cout << "Queue is not empty" << endl;}

特别注意

优先级队列默认是建大堆，也就是元素的值越大，优先级越高。我们可以通过一个传递模板参数来控制优先级的判别。所以，优先级队列在设计的时候用到了3个模板参数，而我们上一章所学习的stack与queue则是2个模板参数，如图：

在这里插入图片描述

	// 默认情况下，创建的是大堆，其底层按照小于号比较priority_queue<int> pq1;// 如果要创建小堆，将第三个模板参数换成greater比较方式// 记得包含greater算法的头文件——#include <functional>priority_queue<int, vector<int>, greater<int>> pq2;

第三个模板参数仅仅只有比较大小的作用，我们也可以自己实现这样一个模板类来传递。像图中Compare这样的类所创建的对象，我们通常称它为——仿函数。因为该类的对象可以像函数一样使用。

🌸什么是仿函数？

仿函数（functor）是一种行为类似于函数的对象，它可以像函数一样被调用。在C++中，仿函数通常是一个类，它重载了函数调用运算符operator()，并且可以像函数一样使用。

仿函数可以被用来封装一些操作或算法，它们可以被传递给其他函数或算法作为参数，或者作为返回值返回给调用者。由于仿函数是一个对象，因此可以在调用它们的过程中保持状态信息，这使得它们可以非常灵活地实现不同的行为。

例如上述的优先级队列又或是库中的sort函数，sort()函数可以接受一个仿函数对象作为第三个参数，这个仿函数对象将被用来比较两个元素的大小关系，这样我们就可以灵活的运用sort函数排序数列为升序或者降序了。

关于仿函数，我们点到为止。

🌸优先级队列的模拟实现

若不了解`堆的结构与使用，可以先看看这篇文章——堆的概念、结构、与实现。

#include <iostream>
#include <vector>
using namespace std;namespace hxy
{// 小于template<class T>class less{public:bool operator()(const T& x, const T& y){return x < y;}};// 大于template<class T>class greater{public:bool operator()(const T& x, const T& y){return x > y;}};// priority_queue类template<class T, class Container = vector<T>,class Compare=less<T>>class priority_queue{// 比较的对象Compare com;// 向上调整void adjust_up(int child){size_t  parent = (child - 1) / 2;while (child > 0){if (com(_con[parent] ,_con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}// 向下调整void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){// 确保child是两个孩子中大/小的那一个if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}public:void push(const T& data){_con.push_back(data);adjust_up(_con.size()-1);}void pop(){// 堆顶元素与堆尾元素互换swap(_con[0],_con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}