【C++】stack和queue以及priority_queue的使用以及模拟实现

目录

前言

一、栈和队列的使用

二、栈和队列的练习题

三、栈和队列的模拟实现

四、优先级队列介绍

五、优先级队列的模拟实现

总结

---

---

前言

        本文主要介绍C++【STL】中的栈(stack)和队列(queue)以及优先级队列(priority_queue)，在栈和队列模拟实现的中会了解到 deque(双端队列)，还有优先级队列的模拟实现过程中了解到仿函数的实现与使用。内容丰富，干货满满，期待你的查阅。

---

一、栈和队列的使用 我在数据结构的文章中已详细介绍了栈和队列，当时也使用C语言进行了模拟实现，而STL中的栈和队列与之前讲的大差不差，因此使用方面简单讲述下即可

stack:

函数声明接口说明push栈顶插入一个数据top返回栈顶元素pop删除一个栈顶元素（没有返回值）empty判空size返回栈中元素个数swap交换两个栈对象

简单演示下栈的循环遍历：后进先出

#include <iostream> #include <stack> using namespace std; int main() { 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; return 0; }

运行结果：  

---

queue:

函数声明接口说明push队尾插入一个元素pop队头删除一个元素front返回队头元素back返回队尾元素empty判空size返回队列中元素个数swap交换两个队列

循环遍历演示：先进先出

#include <iostream> #include <queue> using namespace std; int main() { queue<int> q1; q1.push(1); q1.push(2); q1.push(3); q1.push(4); while (!q1.empty()) { cout << q1.front() << " "; q1.pop(); } cout << endl; return 0; }

 运行结果：

---

二、栈和队列的练习题 1.最小栈

链接：155. 最小栈 - 力扣（LeetCode）

思路：

题目的核心要求是 getMin() 函数的时间复杂度为O(1)。既然要获取栈中的最小元素，那么我们在入栈时就需要进行记录判断最小的元素，因此我们需要设置两个栈，一个栈用来存储所有入栈元素的栈 st，另一个栈专门存入栈的最小元素 minst。我们在 push 函数中，将元素插入st后，首先判断 minst 栈是否为空，为空就直接将元素插入 minst，不为空，则判断入栈元素是否小于 minst 的栈顶元素，小于的话就需要插入到 minst ，反之则不用管。你可能想问万一原来最小的元素出栈了怎么办，这时候就是 pop 函数中需要注意的了，我们需要先判断 st 的栈顶元素是否等于 minst 的栈顶元素，相等则说明是同一个元素，则 minst 和 st 都出栈，这是第二小的元素依旧是 minst 的栈顶元素。所以 getMin 的时间复杂度要想为O(1)，就需要一个最小栈的栈顶记录最小值。（补充：初始化函数不用写，对应自定义类型，编译器会自动调用对应的构造函数）

题解：

class MinStack { public: //不用写，自动调用构造 MinStack() { } void push(int val) { st.push(val); if(minst.empty() || val <= minst.top()) { minst.push(val); } } void pop() { if(st.top()==minst.top()) { minst.pop(); } st.pop(); } int top() { return st.top(); } int getMin() { return minst.top(); } private: stack<int> st; stack<int> minst; }; 扩展问题：如果有大量重复的元素怎么办？ 在上题的基础上，假如元素有大量重复的存在，效率会降低，该怎么解决了呢？解决方法为：新建一个结构体，结构体由一个最小栈和计数变量组成，当遇到相同最小元素时，只需要++计数即可，删除相同的元素时，只要计数大于1，就直接--计数变量即可。

---

2.栈的压入、弹出序列

链接：栈的压入、弹出序列_牛客题霸_牛客网

思路：

题目的意思是，给你两个序列，一个是入栈的顺序，一个是出栈的顺序，让你使用程序判断出栈顺序是否合法。这题我们不能去寻找规律，核心方案就是模拟整个过程，我们需要两个下标去遍历两个序列，如：pushi 循环往后走，将遍历的数据插入到栈中，每插入一个元素后，只要栈还不为空，就循环判断栈顶元素是否与出栈序列的元素相等，相等则出栈然后popi++，不相等则pushi 继续遍历并入栈，直到 pushi 走到入栈序列的尾部就结束循环。最后只需判读栈是否为空即可，因为如果出栈序列合法，则栈一定为空，也就是刚好全部出栈。

题解：

class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { int pushi = 0, popi = 0; stack<int> st; while(pushi < pushV.size()) { st.push(pushV[pushi++]); while(!st.empty() && st.top() == popV[popi]) { st.pop(); ++popi; } } return st.empty(); } };

---

3.逆波兰表达式求值

链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

思路：

这题虽然是中等题，但如果我们了解何为逆波兰表达式的话，这题会非常简单。逆波兰表达式其实就是后缀表达式，我们平时数学上写的表达式是中缀表达式，如下图：简单点说，后缀表达式就是将操作数按原顺序排列，而运算符则按照优先顺序依次放在需要先计算的操作数后面，关于中缀转后缀的过程此题不用管，已经计算好了的，但如果你感兴趣下面扩展中会提到。知道了后缀表达式计算规则，这题就很好写了，我们利用栈的特性，先遍历序列，遇到操作数直接入栈，遇到操作符则先将钱两个操作数出栈并保存，然后用 switch 语句判断操作符为哪一种，再计算后将结果入栈，如此循环直至序列被遍历完。最后返回栈顶结果即可。

题解：

class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(auto& str : tokens) { //操作符 if("+"==str || "-"==str || "*"==str || "/"==str) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); switch(str[0]) { case '+': st.push(left+right); break; case '-': st.push(left-right); break; case '*': st.push(left*right); break; case '/': st.push(left/right); break; } } else//操作数 { st.push(stoi(str)); } } return st.top(); } }; 扩展：中缀转后缀 因为过程稍微有点复杂，我就简单说下转换的思路我们的目标是将一个 string 的中缀表达式转为后缀表达式并存入 vector 中首先参数方面需要一个下标 i ，并且使用引用传值，因为在中缀表达式中存在括号这种需要优先计算的情况，那么就需要使用递归，递归返回时需要从递归遍历结束的位置继续遍历，因此需要一个下标 i 去记录。然后，我们使用 while 循环遍历字符串，遇到操作数则直接尾插到 vector 中，遇到操作符则需要暂存，因为需要判断优先级，如果栈为空则直接插入到栈中，如果下一个操作符优先级大于栈顶操作符，则继续入栈，因为不确定后面还有没有更大的操作符，这里判断优先级需要我们定义一个函数 operatorPrecedence，函数中需要定义一个结构体，_op为操作符，_PD为优先级，优先级按1,2进行区分。前面说到如果栈为空或者操作符的优先级大于栈顶元素则入栈，反之，说明栈顶操作符的优先级需要先计算，因此先将栈顶操作符尾插到 vector ，此时 i 还不能继续++，因为当前操作符还需要继续与栈顶元素比较。然后就是遇到括号的情况了，当我们遍历到左括号时，则先++i，然后递归调用自己，递归相当于重新建立一个函数栈帧，此时递归中的栈是独立的，当递归遍历到右括号时需要返回，返回前需要将栈中剩余的操作符直接出栈。最后当 i 遍历结束后，同样需要将当前栈中的剩余元素全部弹出。这样中缀表达式就成功转化出来了 //判断操作符的优先级 int operatorPrecedence(char ch) { struct opPD { char _op; int _PD; }; static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} }; for (auto& e : arr) { if (e._op == ch) { return e._PD; } } assert(false);//代码不应该执行到这里，不然直接报错 return 0; } //中缀转后缀 void toRPN(const string& s, size_t& i, vector<string>& v) { stack<char> st; while (i < s.size()) { //如果是操作数，直接入v if (isdigit(s[i])) { string num; while (i < s.size() && isdigit(s[i])) { num += s[i++]; } v.push_back(num); } else if (s[i] == '(')//如果遇到括号，需要进行递归 { ++i; toRPN(s, i, v); } else if (s[i] == ')')//遇到收括号，则需要将栈里符号弹出到v { while (!st.empty()) { v.push_back(string(1, st.top())); st.pop(); } ++i; return; } else//如果是操作符 { //如果栈为空或者操作符的优先级大于栈顶元素，入栈 if (st.empty() || operatorPrecedence(s[i]) > operatorPrecedence(st.top())) { st.push(s[i++]); } else//反之,栈顶操作符入v，i不能++，需要继续判断 { char op = st.top(); st.pop(); v.push_back(string(1, op)); } } } //循环结束，弹出栈里符号到v while (!st.empty()) { v.push_back(string(1, st.top())); st.pop(); } }

---

4.用队列实现栈

链接：225. 用队列实现栈 - 力扣（LeetCode）

关于队列的题这里接触的不多，这道题我在C语言数据结构中有详细解答，也就是双队列实现栈，采用来回导的方式。不多废话直接上代码，就当做队列方法使用的练习了

题解：

// 队列实现栈 class MyStack { public: MyStack() {} void push(int x) { if (!q1.empty()) { q1.push(x); } else { q2.push(x); } } int pop() { queue<int>* empQ = &q1; queue<int>* noneQ = &q2; if (!q1.empty()) { empQ = &q2; noneQ = &q1; } while (noneQ->size() > 1) { empQ->push(noneQ->front()); noneQ->pop(); } int ret = noneQ->front(); noneQ->pop(); return ret; } int top() { if (!q1.empty()) { return q1.back(); } else { return q2.back(); } } bool empty() { return q1.empty() && q2.empty(); } private: queue<int> q1; queue<int> q2; };

---

三、栈和队列的模拟实现 1.容器适配器 虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为 容器适配器。

什么是适配器：

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

不理解？没关系，看了模拟实现的代码你就知道为什么叫容器适配器了

---

2.stack的模拟实现 #pragma once #include <deque> namespace txp { 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 { return _con.back(); } //size size_t size() const { return _con.size(); } //判空 bool empty() const { return _con.empty(); } private: Container _con; }; }

---

3.queue的模拟实现 #pragma once #include <deque> namespace txp { template<class T, class Container = deque<T>> class queue { public: //尾插 void push(const T& val) { _con.push_back(val); } //头删 void pop() { _con.pop_front(); } //返回队头元素 T& front() { return _con.front(); } const T& front() const { return _con.front(); } //返回队尾元素 T& back() { return _con.back(); } const T& back() const { return _con.back(); } //size size_t size() const { return _con.size(); } //判空 bool empty() const { return _con.empty(); } private: Container _con; }; }

---

4.说明

根据上面的模拟实现，我们是使用了其他容器作为底层进行封装，将其封装为 “后进先出”的栈 或者 “先进先出”的队列，我们不用像C语言那样自己造轮子，所以说适配器这种设计模式实质上是一种复用。

栈和队列的模拟实现非常简单，因为它的底层是使用了 deque 这种容器的，我们先不说 deque，因为是缺省的模版参数，因此我们也可以自己使用 vector 或 list 进行声明。

例如：

#include <iostream> #include <stack> #include <queue> #include <vector> #include <list> using namespace std; int main() { //stack可以使用vector和list进行适配 stack<int, vector<int>> st1; st1.push(1); st1.pop(); stack<int, list<int>> st2; st2.push(1); st2.pop(); //deque可以使用list进行适配，但不支持vector，因为vector不支持pop_front queue<int, list<int>> q1; q1.push(1); q1.pop(); queue<int, vector<int>> q2; q2.push(1); //q2.pop();error C2039: "pop_front": 不是 "std::vector<int,std::allocator<int>>" 的成员 return 0; }

（queue 不支持vector，详细且查看queue的pop模拟实现）

想必你已经猜到为什么缺省参数选择 deque 而不选择 vector 或者 list 的原因了吧？其实就是因为不够通用，而 deque 就满足这方面需求。

---

5.deque deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。（deque 属于了解型容器，因此不会进行模拟实现）

deque 的接口介绍：

对于以上的接口名称，想必我们已经很熟悉了，STL的容器接口命名都是统一的，所以以上接口的功能与我们前面所学的 string 、vector 、list 是一样的。首先我们有没有发现 deque 的接口非常丰富，可以说它融合了 vector、list 的所有接口，是一个功能非常全面的容器。那么，既然它的功能这么全面，那为什么不能替代 list 和 vector ?我们先带着这个问题来看一下 deque 的底层实现

---

deque 的底层结构：

deque 的底层是由一个一个 buffer 数组组成的当一个数组满后，就另外再开辟一个数组那么这些数组是怎么管理的呢？它们是通过一个中控数组进行管理的，这个中控数组就是一个指针数组。注意观察：我们第一个数组的指针是存储在指针数组的中间位置的，这样做是为了方便头插，可以直接往指针数组前面进行插入数组。当然，当中控数组满了时，中控数组也会进行扩容，但因为是指针数组，不会涉及深拷贝，只需要拷贝地址就行，所以中控数组扩容代价非常低。在这种结构中，当我们使用 [ ] 进行下标访问时，假设每一个数组大小相同并且为10，我们需要访问 pos 下标，这时我们可以 pos /10 计算得到具体哪一个数组，再通过 pos%10 计算得到具体数组中具体的下标位置，是不是比较方便？

---

以上是 deque 底层数据存储的结构，那么这种结构有什么设计缺陷呢？

首先就是 insert 和 erase 接口的实现，这两个涉及中间数组的插入和删除，那么对于 deque 这种结构来说，这中间势必存在性能的牺牲，这里有两种实现方式：1. 挪动中间以及受影响的后面所有数组的数据，这样挪动的代价非常大，效率也很低。但是可以保证每个数组的大小一致，对于 [ ] 访问的效率没什么损失。2. 只挪动需要插入或者删除的那一个数组，插入就将这个数组单独扩容，这样虽然对插入和删除的效率影响不大，但是 [ ] 访问的效率就会直线下降，因为此时每个数组的大小都不确定，因此 [ ] 访问时需要计算所有数组大小，对于 [ ] 的代价非常大。虽然 C++ 官方没有明确规定使用那种方式实现，但是绝大部分编译器厂商采用的是第一种方式，也就是牺牲 insert 和 erase 的性能，换取 [ ] 访问的效率，毕竟 [ ] 使用的场景更多。

 

---

deque 的迭代器设计：

我们先体会下 deque 的迭代器遍历：

#include <iostream> #include <deque> using namespace std; int main() { deque<int> dq{ 1,2,3,4,5,6,7,8,9 }; auto it1 = dq.begin(); while (it1 != dq.end()) { cout << *it1 << " "; ++it1; } cout << endl; return 0; }

运行结果：

---

 使用起来都一样，但是 deque 的迭代器设计可以算是比较复杂的

首先 deque 的迭代器由四个指针组成，三个一级指针，一个二级指针。指针 cur 指向的是当前访问的元素位置，指针 first 指向的是数组开头位置，指针 last 指向的是下一个数组的地址。接下来，我们全面观赏 deque 的结构：从下往上看，首先两个迭代器 start 和 finish，这两个迭代器分别指向中控数组（map）中的头数组和尾数组。deque 的底层就有这两个迭代器进行构成： class deque { iterater start; iterater finish; }

上图中，start 迭代器的 cur 指针指向的是第一个数组的第一个元素，first 同样，last 指向的是第一个数组中最后一个元素，node 指向中控数组中的下一个数组。对于 finish 迭代器与 start 同理。然后，关于迭代器的遍历，操作符 *，它的运算符重载是解引用迭代器中的 cur 指针，也就是数组中当前位置的元素。操作符 ++，它的运算符重载也是让 cur 向前走，如果 cur 指向的位置与 last 相同，那么就解引用 node 二级指针，将当前迭代器的 first 、last、cur 全部重置为下一个数组的位置，最后还需要将 node 更新为中控数组中的下一个数组。

---

以上就是 deque 的迭代器设计，这是多么的巧妙啊，虽然复杂，但是完美的管理起了所有的数组。

接下来，我们再说一下deque的缺陷：

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比vector高的。但是对于 [ ] 的访问效率，deque 是比不过 vector 的。与list比较，deque 底层是连续空间，空间利用率比较高，不需要存储额外字段。但是 list 中间插入和删除数据效率是很高的，这一点 deque 也是比不过 list 的。deque还有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。简单点说 vector 和 list 特点很明显，相当于最强的矛和盾，但是 deque 相比就夹在中间，这就是前面所说为什么 deque 替代不了 vector 和 list。

---

 我们可以通过两段代码，比较下 deque 使用 sort 的排序效率：

#include <iostream> #include <deque> #include <vector> #include <algorithm> using namespace std; void test_op1() { srand((unsigned int)time(0)); const int N = 1000000; vector<int> v1; deque<int> dq1; for (size_t i = 0; i < N; i++) { int e = rand(); v1.push_back(e); dq1.push_back(e); } size_t begin1 = clock(); sort(v1.begin(), v1.end()); size_t end1 = clock(); size_t begin2 = clock(); sort(dq1.begin(), dq1.end()); size_t end2 = clock(); cout << "vector sort: " << end1 - begin1 << endl; cout << "deque sort: " << end2 - begin2 << endl; } void test_op2() { srand((unsigned int)time(0)); const int N = 1000000; deque<int> dq1; deque<int> dq2; for (size_t i = 0; i < N; i++) { int e = rand(); dq1.push_back(e); dq2.push_back(e); } size_t begin1 = clock(); sort(dq1.begin(), dq1.end()); size_t end1 = clock(); size_t begin2 = clock(); vector<int> v; v.assign(dq2.begin(), dq2.end()); sort(v.begin(), v.end()); dq2.assign(v.begin(), v.end()); size_t end2 = clock(); cout << "deque sort: " << end1 - begin1 << endl; cout << "deque copy vector sort,vector back: " << end2 - begin2 << endl; } int main() { test_op1(); test_op2(); return 0; }

运行结果：

test_op1 是测试 vector 和 deque 分别排序一百万个相同的数据需要的时间test_op2 是测试 deque 将一百万个数据拷贝给 vector 排序，vector 排好后再拷回 deque的时间效率。通过结果，很明显可以看到，哪怕经过拷贝这一层消耗，deque 排序的效率完全比不过 vector，所以排序方面，我们不建议直接使用 deque 进行排序。

---

最后在补充下，为什么选择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中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。

---

四、优先级队列介绍

参数 T 为数据类型，参数 Container 为适配容器（默认vector），参数 Compare 为仿函数。

详细介绍：

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

标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector。

需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

省流版：

简单说，优先级队列就是顺序结构的二叉树 ---- 堆。（如果不清楚何为堆，请查看主页数据结构之二叉树篇章）默认情况下就是一个大堆，也就是堆顶为最大值。注意：优先级队列是包含在 queue 头文件下的。（因为优先级队列和栈以及队列一样都是容器适配器，所以没有迭代器）

priority_queue 的接口介绍：

函数声明接口说明priority_queue()构造，支持默认构造和迭代器区间构造push()尾插一个元素pop()删除堆顶元素top()返回堆顶元素size()返回元素个数empty()判空swap()交换两个优先级队列的数据

简单演示优先级队列默认情况下的出堆顺序：

#include <iostream> #include <queue> using namespace std; int main() { priority_queue<int> pq1; pq1.push(5); pq1.push(3); pq1.push(4); pq1.push(1); pq1.push(2); while (!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } cout << endl; return 0; }

运行结果：

因为默认是大堆，所以出队顺序就是从大到小。

---

优先级队列的简单练习题：

链接：215. 数组中的第K个最大元素 - 力扣（LeetCode）

这题使用堆就是一个简单题，我们先建堆，然后根据堆顶为最大值，先将前k-1个最大的元素出堆，最后返回堆顶元素即可。

题解：

class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> pq(nums.begin(), nums.end()); while(--k) { pq.pop(); } return pq.top(); } }; 这题只要我们学过优先级队列并且了解堆就非常简单，所以以后做题如果遇到需要堆的地方，可以直接使用优先级队列进行解决。

---

五、优先级队列的模拟实现 1.基础框架 #pragma once #include <vector> namespace txp { template<class T, class Container = vector<T>> class priority_queue { public: private: Container _con; }; } 我们先不管仿函数，底层默认使用 vector 进行适配。因为是自定义类型，所以不用写默认构造。我们需要自己包含 vector 头文件，因为默认容器就是使用 vector。

---

2.基本接口实现 （1）push //向上调整算法 void AdjustUp(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { //小堆：父节点 > 孩子节点，交换 //大堆：父节点 < 孩子节点，交换 if (_con[parent] < _con[child]) { std::swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //尾插 void push(const T& val) { _con.push_back(val); AdjustUp(_con.size() - 1); } 我在C语言数据结构中已讲解堆的实现，因此不再重复。我们在堆中插入数据时就需要借助 “向上调整算法” 进行调整建堆，向上调整算法就是将新插入的数据与堆中数据进行比较，以保持堆顶为最大值（默认是大堆）。

---

（2）pop //向下调整算法 void AdjustDown(size_t parent) { //左孩子 size_t child = 2 * parent + 1; while (child < _con.size()) { //小堆：找左右孩子中小的值 //大堆：找左右孩子中大的值 if (child + 1 < _con.size() && _con[child] < _con[child + 1]) { child++; } //小堆：父节点 > 孩子节点, 交换 //大堆：父节点 < 孩子节点，交换 if (_con[parent] < _con[child]) { std::swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } //头删 void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } pop 对应着头删，头删不是直接删除，而是先将头部数据与尾部数据进行交换，再尾删以达到删除数据效果，这样删除效率高，但是这样会破坏堆的性质，因此需要 “向下调整算法进行调整”。向下调整算法就是调整堆顶数据，将堆顶数据与下面数据比较，将最大值交换上去。（温馨提醒：如果不懂该算法可以移步主页数据结构之二叉树的文章）

---

（3）top、empty、size //top const T& top() { return _con[0]; } //判空 bool empty() { return _con.empty(); } //返回size size_t size() { return _con.size(); } 这三个接口可以直接使用适配容器的接口进行实现。

---

3.仿函数 以上，我们已经实现了一个大堆，但是大堆只能返回最大值，当我们需要小堆的时候，我们就需要自己到代码中去调节比较操作符，这样会很麻烦，所以有没有一种方法可以方便调整比较操作符呢？这时，就是仿函数存在的意义了

仿函数简介：

仿函数其实就是一个类，只不过类中重载了 () 这个运算符，我们之前重载过 += 这样的操作符，使用时只需要对象名+=就可以进行使用了，而（）也一样，当我们重载了小括号后，就可以使用对象名() 进行调用重载函数了。这时，我们想解决上面问题，就可以在重载的()函数中写一个比较函数，将堆中需要进行比较的地方换成这个仿函数，我们事先写好两个仿函数，一个比较大于，一个比较小于，在官方中，大于的仿函数叫 greater，小于的仿函数叫 less。

实现仿函数类：

//仿函数 template<class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> struct greater { bool operator()(const T& x, const T& y) { return x > y; } }; 这时，我们再将堆的模版参数加上一个 class Compare = less<T>，在官方中，传小于的仿函数是实现大堆，传大于的仿函数实现的是小堆，因此我们实现的堆是与官方看齐的，虽然这一点设计的感觉不太好。最后将堆中 “向上调整算法” 和 “向下调整算法”’ 中需要比较孩子节点和父节点等地方进行替换。这样比较大小就由我们传的仿函数进行控制了。

调整后的优先级队列：

#pragma once #include <vector> namespace txp { template<class T, class Container = vector<T>, class Compare = less<T>> class priority_queue { public: //向上调整算法 void AdjustUp(size_t child) { Compare com;//仿函数对象 size_t parent = (child - 1) / 2; while (child > 0) { //小堆：父节点 > 孩子节点，交换 //大堆：父节点 < 孩子节点，交换 //if (_con[parent] < _con[child]) if(com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //尾插 void push(const T& val) { _con.push_back(val); AdjustUp(_con.size() - 1); } //向下调整算法 void AdjustDown(size_t parent) { Compare com;//仿函数对象 //左孩子 size_t child = 2 * parent + 1; while (child < _con.size()) { //小堆：找左右孩子中小的值 //大堆：找左右孩子中大的值 //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; } //小堆：父节点 > 孩子节点, 交换 //大堆：父节点 < 孩子节点，交换 //if (_con[parent] < _con[child]) if(com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } //头删 void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } //top const T& top() { return _con[0]; } //判空 bool empty() { return _con.empty(); } //返回size size_t size() { return _con.size(); } private: Container _con; }; //仿函数 template<class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> struct greater { bool operator()(const T& x, const T& y) { return x > y; } }; }

---

4.补充构造函数 优先级队列我们已经大差不差的实现了，但是还有一个重要的功能没有实现，就是使用迭代器区间进行构造。注意这可不是简单的拷贝插入，而是需要进行建堆操作，如果你了解堆这个数据结构，你就一定知道堆排序，堆排序之前就需要对数组元素进行建堆，以保证数据是大堆或者是小堆的结构。在我们之前堆排序的学习中，我们知道建堆和堆排序都是使用向下调整算法进行实现的，因为向下调整建堆的效率整体是高于向上调整的。

实现迭代器区间构造：

//强制生成默认构造 priority_queue() = default; //迭代器构造 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first, last) { //建堆 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { AdjustDown(i); } } 详细建堆解释在主页二叉树文章中有详细介绍。简单点说就是从最后一个父节点开始，逐渐往上进行建堆，最后使其整体成为一个大堆或者小堆。需要注意的是，当我们显示的写了构造后，编译器是不会自动生成默认构造了，如果我们不想自己手动去写默认构造，可以加上上面第一行代码，强制编译器生成一个默认构造。

---

5.完整代码 #pragma once #include <vector> namespace txp { 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() - 1 - 1) / 2; i >= 0; i--) { AdjustDown(i); } } //向上调整算法 void AdjustUp(size_t child) { Compare com; size_t parent = (child - 1) / 2; while (child > 0) { //小堆：父节点 > 孩子节点，交换 //大堆：父节点 < 孩子节点，交换 //if (_con[parent] < _con[child]) if(com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //尾插 void push(const T& val) { _con.push_back(val); AdjustUp(_con.size() - 1); } //向下调整算法 void AdjustDown(size_t parent) { Compare com; //左孩子 size_t child = 2 * parent + 1; while (child < _con.size()) { //小堆：找左右孩子中小的值 //大堆：找左右孩子中大的值 //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { child++; } //小堆：父节点 > 孩子节点, 交换 //大堆：父节点 < 孩子节点，交换 //if (_con[parent] < _con[child]) if(com(_con[parent], _con[child])) { std::swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else { break; } } } //头删 void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } //top const T& top() { return _con[0]; } //判空 bool empty() { return _con.empty(); } //返回size size_t size() { return _con.size(); } private: Container _con; }; //仿函数 template<class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> struct greater { bool operator()(const T& x, const T& y) { return x > y; } }; }

---

6.仿函数使用演示

我们同时使用自己实现的优先级队列和官方的优先级队列进行演示：

#include <iostream> #include <queue> #include "PriorityQueue.h" using namespace std; int main() { vector<int> v = { 9,6,3,2,5,8,1,4,7 }; //官方 //默认建大堆 priority_queue<int> pq1(v.begin(), v.end()); while (!pq1.empty()) { cout << pq1.top() << " "; pq1.pop(); } cout << endl; //建小堆 priority_queue<int, vector<int>, greater<int>> pq2(v.begin(), v.end()); while (!pq2.empty()) { cout << pq2.top() << " "; pq2.pop(); } cout << endl; //我们自己实现的 //默认建大堆 txp::priority_queue<int> my_pq1(v.begin(), v.end()); while (!my_pq1.empty()) { cout << my_pq1.top() << " "; my_pq1.pop(); } cout << endl; //建小堆 txp::priority_queue<int, vector<int>, txp::greater<int>> my_pq2(v.begin(), v.end()); while (!my_pq2.empty()) { cout << my_pq2.top() << " "; my_pq2.pop(); } cout << endl; return 0; }

运行结果：

最后需要注意的一点是，当我们需要给第三个模版参数传值时，前两个必须也上传。

---

总结

        以上就是本文的全部内容了，博主熬夜码字不易，感谢支持！