介绍 C++ STL 中的容器适配器 Stack、Queue 和 Priority Queue。Stack 遵循后进先出原则，支持尾插尾删；Queue 遵循先进先出原则，支持头删尾插。Priority Queue 基于堆实现，默认大堆。文章详细讲解了各容器的接口、使用场景及模拟实现，重点分析了底层容器选择（如 deque 作为 Stack/Queue 默认容器）的原因。结合最小栈、栈弹出序列、逆波兰表达式、二叉树层序遍历等经典算法题，深入理解数据结构在实际编程中的应用。
【说明】
- stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
- stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部 (即栈顶) 被压入和弹出。
- stack 的底层容器，可以是任何标准的容器类模板，或者一些其他特定的容器类。
- 这些容器类应该支持以下操作：empty（判空）、back（获取尾部元素）、push_back（尾部插入）、pop_back（尾部删除）。
- 标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器，默认使用 deque。
| 函数说明 | 接口说明 |
|---|---|
| stack() | 构造空的栈 |
| empty() | 检测 stack 是否为空 |
| size() | 返回 stack 中元素的个数 |
| top() | 返回栈顶元素的引用 |
| push() | 将元素 val 压入 stack 中 |
| pop() | 将 stack 中尾部的元素弹出 |
最小栈是一个栈，支持后进先出，但是增加了一个接口——获取最小元素。要求时间复杂度 O(1)，不能是 O(N) 遍历。
**思路 1：**用一个 min 记录一下最小元素——每次入栈的时候，都用入栈元素跟 min 比较一下，如果比 min 小就更新 min。
**问题 1：**删栈顶元素之后，min 该如何更新？得遍历一遍，但栈不允许遍历（没有提供迭代器），就算允许遍历，时间复杂度也是 O(N)。
【注意】 minst 栈顶就是当前最小元素，minst 栈顶之下是曾经的最小元素，栈顶弹出后下面的'曾经最小元素'才有机会重新成为'当前最小元素'。入栈元素小于等于 minst 栈顶元素，都得入栈 minst，得保证两边的最小元素的个数一致，因为删的时候是一起删的。
用 C++ 的代码，就不需要造轮子了，也不用写构造，全是自定义类型成员变量，默认构造就可以。
// 最小栈类
// 成员变量：st、minst
// 成员函数：……
class MinStack {
public:
// 入数据
void push(int x) {
// 只要是压栈，先将元素保存到_elem 中——正常栈，直接入
_elem.push(x);
// 如果 x 小于_min 中栈顶的元素，将 x 再压入_min 中——min 栈判断一下再入
if (_min.empty() || x <= _min.top())
_min.push(x);
}
// 出数据
void pop() {
// 如果_min 栈顶的元素等于出栈的元素，_min 顶的元素要移除——min 栈判断一下再出
if (_min.top() == _elem.top())
_min.pop();
_elem.pop(); // 正常栈，直接出
}
int top() { return _elem.top(); } // 获取栈顶元素
int getMin() { return _min.top(); } // 获取最小元素
private:
// 保存栈中的元素
std::stack<int> _elem;
// 保存栈的最小值
std::stack<int> _min;
};
不用写构造——编译器生成的默认构造，对自定义类型 stack 会去调它的默认构造。
入栈和出栈序列匹配，之前做过选择题。一个入栈序列，会有多个与之匹配的出栈序列。
任何一个数据都是入栈之后，再出栈。这道题感觉简单，写得稍有不慎，就会写成一个复杂题。
一定记住不要直接把入栈序列、出栈序列直接拿来比较。而是任何一个数据都保证它是入栈之后，再去出栈，就没问题。
入完栈之后再判断栈顶元素出不出，而不是还没入栈就直接判断。
直到入栈序列 push_st（数组的形式），本次入栈 st 的元素 num，恰好等于出栈序列 pop_st（数组的形式）的首元素，就执行出栈，按着出栈序列 pop_st 的顺序进行出栈。
匹配到情况 b，就执行操作 1。 匹配到情况 a，就执行操作 2。
出完 4，用 3 和 5 比较，不相等，符合情况 b，下一步是操作 1。入栈 5。
再比较，若相等，出完继续比。一直相等一直比。
结束条件：栈 st 空了。
不相等就继续入，一直不等一直入。
相等出完继续比，一直相等一直比。
5 入栈，相等再出栈。
不相等，要再入数据，但是入栈序列已经空了。
【结束条件】 入栈序列必然已经结束了；① 上面这种情况——匹配的时候：出栈序列也结束了，同时栈空了（栈空 or 出完，都可以验匹配）② 下面这种情况——不匹配的时候：出栈序列没结束，同时栈也没空（栈非空 or 没出完，都可以验不匹配）
如果把入栈序列（数组）和出栈序列（数组）直接比较，不相等就++，而不是借助一个第三方的栈这样一个数据结构来辅助判断，就很麻烦了。
算法能力跟看得算法课多少没多大关系，不是看了就会了，重要的是学会这些方法和思路。
逻辑梳理顺了，代码就很好写了，大框架是这样，无非是一些细节上面的控制。这些算法题，代码已经不那么重要了，重要的是思路。画图把思路理清楚。
class Solution {
public:
bool IsPopOrder(vector<int> pushV, vector<int> popV) {
// 入栈和出栈的元素个数必须相同
if (pushV.size() != popV.size()) return false;
// 用 s 来模拟入栈与出栈的过程
int outIdx = 0; // 当前出栈序列的下标
int inIdx = 0; // 当前入栈序列的下标
stack<int> s;
while (outIdx < popV.size()) {
// 如果 s 是空，或者栈顶元素与出栈的元素不相等，就入栈
while (s.empty() || s.top() != popV[outIdx]) {
if (inIdx < pushV.size())
s.push(pushV[inIdx++]);
else
return false;
}
// 栈顶元素与出栈的元素相等，出栈
s.pop();
outIdx++; // 下标迭代
}
return true;
}
};
栈为空：所有数据都匹配上了。栈不为空：有数据没匹配上。
class Solution {
public:
int evalRPN(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 '/': // 题目说明了不存在除数为 0 的情况
s.push(left / right); break;
}
}
}
return s.();
}
};
……
从栈的接口中可以看出，栈实际是一种特殊的 vector，因此使用 vector 完全可以模拟实现 stack。
#include<vector>
namespace bite {
template<class T>
class stack {
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
std::vector<T> _c;
};
}
适配器的作用就是用于转换的，以电力系统为例，在外传输需要转换到特高压降低损耗，接入家庭需要转换 220V，各种功率电器使用需要使用电源适配器转换成对应的电压。
同理，为了满足不同场合的不同需求，栈的实现也要提高兼容性。
用 vector（list）来适配，只提供尾插尾删，封装一下，就成了一个顺序栈（链栈）。
但是这样用 list _lt 的方式，就写死了，没法灵活适配。
所以它在这增加一个模版参数——容器 Container，用来提供合适的容器，适配出一个栈。
模版参数平时没有具体含义的时候，就叫 T（Type），这里有具体含义，就可以使用它的含义。
这样构造就不用写了，直接使用自定义类型的默认构造。
栈的设计打开了一种新的设计模式：之前设计一个数据结构，就要自己一笔一画去写，一点一点去搓。而现在只需要对其他合适的数据结构封装一下，转换一下就完成了我需要的数据结构，而且依靠模版参数的泛型编程，灵活适配不同容器来作底层架构，从而适配不同的应用场景。
代码测试。
在表层，使用的 stack 都是一个后进先出的特性的容器。
但是底层数据结构却很不一样。
库里面的 stack 的使用，可以不用传第 2 个参数，stack st 就可以了，所以我们也可以给到一个缺省参数。
模版参数和函数参数很类似，都是实参传递给形参。模版参数是<>尖括号，函数参数是圆括号 ()。模版参数传的是类型，函数参数传的是对象。模版参数和函数参数一样，都可以给缺省值，只是这个地方给的缺省值是一个类型。
队列也是类似的，也可以这样实现。
vector 支持尾插尾删，不支持头插头删（虽然有 insert、erase 但慎用）list 支持尾插尾删头插头删，但是不支持 [] 访问。 deque 支持头插头删尾插尾删，和 [] 访问。
【说明】
- 队列是一种容器适配器，专门用于在 FIFO 上下文 (先进先出) 中操作，其中从容器一端插入元素，另一端提取元素。
- 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
- 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：empty（检测队列是否为空）、size（返回队列中有效元素的个数）、front（返回队头元素的引用）、back（返回队尾元素的引用）、push_back（在队列尾部入队列）、pop_front（在队列头部出队列）。
- 标准容器类 deque 和 list 满足了这些要求。默认情况下，如果没有为 queue 实例化指定容器类，则使用标准容器 deque。
| 函数声明 | 接口说明 |
|---|---|
| queue() | 构造空的队列 |
| empty() | 检测队列是否为空，是返回 true，否则返回 false |
| size() | 返回队列中有效元素的个数 |
| front() | 返回队头元素的引用 |
| back() | 返回队尾元素的引用 |
| push() | 在队尾将元素 val 入队列 |
| pop() | 将队头元素出队列 |
……
思路：先进先出，上一层的父结点出去的时候，带入下一层它的子结点。
例如：先入 3，3 出的时候带入 9、20，9 出的时候带入 9 的子树（NULL），20 出的时候带入 15、7
这道题是进阶版：要求每一层都存到一个数组里面，总的存成一个数组，即二维数组。
这样子的话用 C 语言写起来就很麻烦
动态返回二维数组，上次 vector<vector<……>> 已经说过这个问题了。
问题来了：什么时候一行就走完了呢？？？
先来实现层序遍历入队列。
问题：怎么一层一层地取。怎么知道一个数据是那一层的呢？？？
**思路 1：**再搞一个队列存层数——队列内每一个元素，都在另一个队列中对应的位置存放着它对应的层数。
常规队列存完 3，再搞一个队列存它的层数 1。
3 出去的时候，1 也就跟着出。同时带入下一层的数据，同时跟着入层数 2。
元素 9 和层数 2 出去，就带入元素 15 和层数 3。
评价：这种思路可行，但是这种思路在操控上可能略复杂。因为每一层的数据你知道它是第几层以后，你还要把它放到 vector 里面去，并且你是第 1 层的要放到第 0 行的 vector。还得把 vector 提前 resize 好，不然的话，放数据的时候，用插入数据就会频繁扩容。
思路 2：直接在这个地方用一个 levelsize（每一层的数据个数）变量控制，用 while 循环控制一层一层出。
第一层一个数据，levelsize 为 1，用一个 while 循环控制，出完就减到 0。
因为 queue 的接口中存在头删和尾插，因此使用 vector 来封装效率太低，故可以借助 list 来模拟实现 queue，具体如下：
#include <list>
namespace bite {
template<class T>
class queue {
public:
queue() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_front();}
T& back() {return _c.back();}
const T& back()const {return _c.back();}
T& front() {return _c.front();}
const T& front()const {return _c.front();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
:
std::list<T> _c;
};
}
queue 的适配容器可以选 list、deque，默认是 deque。
使用 vector 来适配可能会报错——先进先出，需要头删，vector 不（直接）支持头删——效率低。
注意 queue 提供的接口是 front，而不是 top。
而 vector 没有支持 pop_front，用 vector 来适配会报错——避免使用低效的方式来适配队列。
适配器：适配器是一种设计模式。
什么是设计模式？
以兵法为例，第一个比较著名的兵法就是《孙子兵法》。
最开始打仗就是拼谁的人多，后面发现打仗也可以有一定的套路，不是说人多一定能赢。
设计模式类似于兵法，最开始大家写代码的时候都是随意写，后面语言趋于成熟后，就形成了一定特定的套路——编程模式。
后面大家在写程序的时候，除了要把功能实现，还讲究一个代码的可维护性。
日常的代码写好了之后，后面就不会再去管了，工作中的代码要持续地去维护，修复用户深度使用过程中出现的各种各样的 bug、优化效率、开发新的需求、……等等。
这个时候如果代码的可维护性不高，就会导致后续在维护的时候，引发连锁问题，各种问题冒出来，后面就出现了软件工程这门学科，提出了低耦合、高内聚、设计模式等等这样的概念。
现在已经学过的有：**迭代器模式；**适配器模式。
while 的条件是不等于，而不是小于，因为数组、字符串可以说前面的元素的指针小于最后的指针，但链表没有这样的规律。
第一层封装：想给你访问的设置成公有，不想给你访问的设置成私有，把数据和方法都封装到类里面。第二层封装：不管底层结构的差异巨大，在里面封装一个统一的访问方式（各种容器的自己的实现可能是原生指针，可能是自定义类型）——typedef …… iterator，在外层提供统一的访问接口——begin()、end()、*(原生指针本来就可以，自定义类型需要重载运算符)。
C 语言也可以实现迭代器，只是不支持运算符重载——*重载，但是支持 typedef。
故而实现起来没那么方便，可读性也不是很高。
C 语言是面向过程的语言，*重载是面向对象的思维，面向过程的话可以使用函数的方式：ListIterEqual(it,end())、getData()、next()）。
面向对象支持运算符重载，可以把迭代器封装得更类似于指针，用法上几乎和指针一致。
C 语言也可以模拟出成员函数的概念——用函数指针的方式。
结构体可以用函数指针模拟实现成员函数，函数指针可以直接加上 () 填入参数就调用的。
上面的 C 语言迭代器就可以用 it.get()、it.next()。
迭代器模式，为各种容器提供了统一的访问模式。
像 Python 这样的其他语言，可能没有迭代器的概念，只有范围 for，其底层还是迭代器，在迭代器上又加了一层封装。
迭代器模式的核心思想：封装以后提供统一的访问方式。（所有容器的访问都可以使用这种方式）适配器模式的核心思想：封装转换——一个容器的底层结构是什么，不是写死的，是由第二个模版参数决定的，但其表现出来的功能是不变的。
适配器模式：用现成的容器来封装出一个新的具有特定功能的容器，这个具有特定功能的容器可以用不同的基础容器来适配，从而产生在基础功能之外的特点。
用不同的容器适配出来的栈，底层完全不同，而表现的功能类似——后进先出。
设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结，该种模式是将一个类的接口转换成客户希望的另外一个接口。
虽然 stack 和 queue 中也可以存放元素，但在 STL 中并没有将其划分在容器的行列。
而是将其称为容器适配器，这是因为 stack 和队列只是对其他容器的接口进行了包装，STL 中 stack 和 queue 默认使用 deque，比如：
**容器适配器都没有提供迭代器；****因为不支持使用迭代器访问；****容器适配器对其元素的访问是有严格限制的；**从哪里插入、从哪里弹出都是有严格限制的。
deque 在功能上是 vector 和 list 的结合体，所以很多适配器的默认容器都是 deque。vector 没有头删（插）；list 没有 [] 重载；deque 设计来替代 vector 和 list，但是没有成功，数据结构的基础学习还是'顺序表'、'链表'。（类似于骡子：驴 + 马）
vector 和 list 除了功能上的差异，它们在结构上也是两种极致的结构——极致的连续 VS 极致的离散
**deque（Double-End Queue，双端队列）：是一种双开口的'连续'空间的数据结构。**双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)。与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。
deque 在结构上类似于 vector。
第一段 buff 的地址不是存储在中控数组的首元素，而是中间，这样头插元素（头插 buff 数组）之后可以把头插的 buff 数组地址放到之前第一段 buff 数组地址的前面。
deque 的缺陷：
这就是说想：
STL 库选择了'数据挪动'的方式，保持 buff 大小一致。
不过总的来说，[] 的效率不如 vector，erase/insert 的效率不如 list。
算法和数据都一样，不同的是容器的结构，可以看到效率上的差别还是比较大的。
可以看到 deque 的 [] 访问速度不够极致。
头尾插删的效率不错，因为不需要扩容，直接再开 buff 数组就可以了。
中控数组有可能会扩容——代价很低，只需要拷贝指针就可以了。
不是高频访问，而是偶尔访问，那么 deque 的 [] 也还行。
但是大量访问——比如排序（访问数据来比大小），deque 相比于 vector 就很慢了。
**【结论】**经常在头尾插入删除，偶尔下标访问，就可以使用 deque。stack 和 queue 使用 deque 作默认容器就比较合适。deque 相比于 vector 不需要扩容；deque 相比于 list 有更好的 CPU 高速缓存效率优势；主流的数据存储还是使用顺序表、链表。
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组，其底层结构如下图所示：
**双端队列，底层是一段假象的连续空间，实际是分段连续的，为了维护其'整体连续'以及随机访问的假象，落在了 deque 的迭代器身上，**因此 deque 的迭代器设计就比较复杂，如下图所示：
deque 的成员变量主要就是两个迭代器，此外还有一个中控数组成员和 size 成员。
那 deque 是如何借助其迭代器维护其假想连续的结构呢？
cur：指向当前位置；
first：指向当前 buff 的第一个有效空间；
last：指向当前 buff 的最后一个有效空间的下一个位置；
size：每个 buff 数组的统一大小。
start 的 cur：指向第一个有效数据；
finish 的 cur：指向最后一个有效数据的下一个位置；
来看看 start 和 finish 的工作原理：
start 的左边不一定有数据，finish 的右边不一定有数据。
如果没有头插过，那么 cur-first==0，偏移量直接就是 n，直接让 cur+=n。
如果头插过 2 次（buff 大小 10），那么 cur-first==8：
**【优势】**与 vector 比较：deque 在头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必 vector 高的。**与 list 比较：**其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque 有一个致命缺陷：不适合遍历，因为在遍历时，deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历。
因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多。而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。
stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以；queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list。但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：
结合了 deque 的优点，而完美的避开了其缺陷。
#include<deque>
namespace bite {
template<class T, class Con = deque<T>> //template<class T, class Con = vector<T>> //template<class T, class Con = list<T>>
class stack {
public:
stack() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_back();}
T& top() {return _c.back();}
const T& top()const {return _c.back();}
size_t size()const {return _c.size();}
bool empty()const {return _c.empty();}
private:
Con _c;
};
}
#include<deque>
#include <list>
namespace bite {
template<class T, class Con = deque<T>> //template<class T, class Con = list<T>>
class queue {
public:
queue() {}
void push(const T& x) {_c.push_back(x);}
void pop() {_c.pop_front();}
T& back() {return _c.back();}
const T& back()const {return _c.back();}
T& front() {return _c.front();}
const T& front()const {return _c.front();}
size_t size()const {return _c.size();}
bool { _c.();}
:
Con _c;
};
}
**priority_queue：**有一个 container 参数，需要传一个容器去适配，所以优先级队列是一个容器适配器。
priority_queue 默认使用 vector 进行适配。
【问】为什么 stack 和 queue 默认用 deque 去适配，而 priority_queue 默认用 vector？
【答】因为 priority_queue 需要大量使用 [] 访问——底层是（二叉）堆。最大元素：大堆；最小元素：小堆；
**STL 库没有现成的堆，有堆算法；**要使用堆就直接使用优先级队列——优先级队列就是堆；
【说明】
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中位于顶部的元素）。
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的'尾部'弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：empty()（检测容器是否为空）、size()（返回容器中有效元素个数）、front()（返回容器中第一个元素的引用）、push_back()（在容器尾部插入元素）、pop_back()（删除容器尾部元素）。
- 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector。
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。
优先级队列默认使用 vector 作为其底层存储数据的容器；在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构；因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。堆的核心操作：取堆顶；插入堆顶；删除堆顶。
注意：默认情况下 priority_queue 是大堆。
| 函数声明 | 接口说明 |
|---|---|
| priority_queue()/priority_queue(first, last) | 构造一个空的优先级队列 |
| empty() | 检测优先级队列是否为空，是返回 true，否则返回 false |
| top() | 返回优先级队列中最大 (最小元素)，即堆顶元素 |
| push() | 在优先级队列中插入元素 x |
| pop() | 删除优先级队列中最大 (最小) 元素，即堆顶元素 |
- 默认情况下，priority_queue 是大堆。
priority_queue 支持迭代器区间初始化。
优点：直接建堆，不用挨着挨着 push。
【注意】如果数据不在 vector 里面，而是在数组 int arr[10] 里面，也可以用迭代器构造，同时数组也可以用 sort 排序。
**【注意】****数组——连续的物理空间，可以直接传原生指针给迭代器参数。**实现 vector 的迭代器就可以直接使用原生指针。
【注意】建小堆需要传仿函数。
【注意】要显式给第 3 个模版参数，就要先把前 2 个模版参数给出来。
#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;
}
- 如果在 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(, , ));
cout << q() << endl;
priority_queue<Date, vector<Date>, greater<Date>> q2;
q((, , ));
q((, , ));
q((, , ));
cout << q() << endl;
}
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 将数组中的元素先放入优先级队列中
priority_queue<int> p(nums.begin(), nums.end());
// 将优先级队列中前 k-1 个元素删除掉
for(int i = 0; i < k-1; ++i) {
p.pop();
}
return p.top();
}
};
priority_queue 的底层结构就是堆，因此此处只需对堆进行通用的封装即可。
逻辑上是二叉树，物理上是数组。
**【堆的插入】——'两步走'**数据尾插数据向上调整
// 向上调整——需要支持下标访问（计算父节点）
void adjust_up(int child) {
int parent = (child - 1) / 2;
while (child > 0) {
// 用小于比较实现大堆——如果父亲小于孩子，就需要向上调整孩子
if (_con[parent] < _con[child]) {
swap(_con[parent], _con[child]);
// 迭代——更新孩子坐标，重新计算孩子的父亲
child = parent;
parent = (child - 1) / 2;
}
// 否则就结束循环
else break;
}
}
【注意】循环结束条件是 child==0 而不能是 parent==0，因为当 parent==0 了还要走完下一轮比较。
**【堆的删除】——'三步走'**头尾互换删除最后一个元素向下调整
构造函数可以不用写，优先级队列的简单实现就结束了。
// 迭代区间初始化
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last) {
// 全部插入——数据插入完，还不是堆
while (first != last) {
_con.push_back(*first);
// 调用优先级队列的 push_back，相当于向上调整建堆——效率略低于向下调整建堆
++first;
}
// 向下调整建堆——从最后一个父节点（非叶子结点）开始
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) // 最后一个结点 size-1 的父节点就用'先减一后除二'的公式，就是 (size-1-1)/2
{
adjust_down(i);
}
}
【之前建小堆的思路】改变 adjust_down/up 的 if 括号内比较表达式的 < 或 > 符号。
C 语言通过传递函数指针来解决这个问题，C++ 不喜欢使用函数指针（太复杂）。
C++ 给出了一个新概念——仿函数（函数对象）。
仿函数（函数对象）：重载了 operator() 的类，用类实例化的对象可以像函数一样使用。operator()：参数个数和返回值根据需求确定，不固定，很灵活。
仿函数可以考虑实现成 struct——默认是公有。
仿函数的作用：传值给这个对象，可以完成预定任务。
注意类型匹配：
仿函数建议实现成类模版。
operator() 的特点：参数个数、返回值——根据需求确定，不固定。相比于之前学过的一些运算符重载函数而言，更加灵活。这个特点决定了它的功能非常多样化。
sort 排升序、降序的仿函数设计也是这样子搞的：
用这个模版参数（仿函数的类）实例化出对象，用这个对象实现比较大小。
【模版的思想】用你传递的具体的模版参数类型，实例化出特定的东西。
【大堆 or 小堆】通过仿函数控制，仿函数控制堆里面的比较逻辑。
【仿函数 vs 函数指针】仿函数就是类 + 运算符重载，相比于函数指针是更简单的。
在优先级队列（堆）中存放自定义类型：
改为存储日期类的指针：
结果并不是按日期类的升序，因为是按日期类的指针的升序。
new（malloc）是带有随机性的，并不是后 new 的空间的地址一定大。
最终打印结果每次运行都不一样，有 30-28-29、28-29-30、28-30-29、29-30-28、29-28-30……。
此时就可以写一个仿函数——自定义建堆方式：按插入数据的解引用的值比较建堆。
除了控制简单的大于小于比较逻辑，我们还可以控制仿函数实现更复杂的比较逻辑，来建造特定的堆。
仿函数在这里就充当了一种回调函数的作用。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online