💭 写在前面

学完 stack 和 queue 后，以后我们再需要用栈和队列的地方我们就不用自己去实现了，直接用就行。它们是通过容器适配器去实现的，本章我们先去学习如何去使用它们。此外我们还要讲解优先级队列 priority_queue 和双端队列 deque，deque 我们下一章实现 stack 和 queue 的时候会用到，所以放在这一章先讲解一下，至于 deque 涉及到的 "仿函数" 概念我们会再下一章讲实现的时候重点讲解！

Ⅰ. stack

0x00 栈的概念

栈是一种特殊的线性表，只允许在固定的一端进行插入和删除元素的操作。

进行数据插入的删除和操作的一端，称为 栈顶 。另一端则称为 栈底 。

栈中的元素遵守后进先出的原则，即 LIFO原则（Last In First Out）。

压栈：栈的插入操作叫做 进栈 / 压栈 / 入栈 ，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

0x01 stack 的介绍

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

stack 是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行 元素的插入与提取操作。

stack 是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定 的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。

标准容器 vector、deque、list 均符合这些需求，默认情况下，如果没有为 stack 指定特定的底层容器， 默认情况下使用 deque。

stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：

empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作

[ Constructs a stack container adaptor object. ]

通过观察文档我们不难发现，接口相较于之前的 string、vector 和 list 少了很多。

它甚至连拷贝构造和析构都没有自己实现，然而这些都得益于容器适配器的使用。

不难发现， stack、queue 也没有迭代器，这也不难理解，

毕竟能让你随便遍历，不就破坏了栈和队列的原则了。

0x02 stack 的使用

💬 代码演示：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

0x00 队列的概念

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

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

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

0x01 queue 的介绍

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

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端 提取元素。

队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列，从队头出队列。

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

底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作：

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

0x02 queue 的使用

💬 代码演示：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;
}

🚩 运行结果：1 2 3 4

Ⅲ. 优先级队列 - priority queue

0x00 priority_queue 的介绍

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

优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素（优先队列中位于顶部的元素）。

优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

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

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

底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭 代器访问，并支持以下操作：

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

0x01 优先级队列的使用

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

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

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

值得注意的是，priority_queue 默认为大根堆。

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

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

（仿函数我们放到下一章，实现优先级队列时详细讲解，现在只需要知道如何使用即可）

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

💬 代码演示：以大的优先级

#include <iostream>
#include <queue>
#include <functional>  // greater算法的头文件
using namespace std;
void test_priority_queue() {
    priority_queue<int> pQ;
    pQ.push(2);
    pQ.push(5);
    pQ.push(1);
    pQ.push(6);
    pQ.push(8);
    while (!pQ.empty()) {
        cout << pQ.top() << " ";
        pQ.pop();
    }
    cout << endl;
}

🚩 运行结果：8 6 5 2 1

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

💬 代码演示：以小的优先级

我们前面说了，优先级队列默认使用 vector 作为其底层存储数据的容器的：

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

所以你也可以使用其他容器去存储 priority_queue，比如 list ：

priority_queue<int, vector<int>, greater<int>> pQ;
#include <iostream>
#include <queue>
#include <functional>  // greater算法的头文件
using namespace std;
void test_priority_queue() {
    priority_queue<int, vector<int>, greater<int>> pQ;
    pQ.push(2);
    pQ.push(5);
    pQ.push(1);
    pQ.push(6);
    pQ.push(8);
    while (!pQ.empty()) {
        cout << pQ.top() << " ";
        pQ.pop();
    }
    cout << endl;
}

🚩 运行结果：8 6 5 2 1

🔑 解读：我们在定义优先级队列时主动去传 greater<int> 即可令该优先级队列以小的优先级高。

📌 注意事项：

如果你想传第三个模板参数，你必须得先传第二个（下面是定义，仔细观察缺省值部分）

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

所以如果你想让优先级队列以小的优先级高，你不能这么做：

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

Ⅳ. 双端队列 - double ended queue

0x00 deque 的介绍

deque 是一种双开口的 "连续" 空间的数据结构，deque 可以在头尾两端进行插入和删除操作。

且时间复杂度为 ，与 vector 相比，头插效率高，不需要搬移元素。

与 list 相比，deque 的空间利用率更高。

0x01 deque 的实现原理

deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。

实际的 deque 类似于一个动态的二维数组，其底层结构如下所示：

双端队列底层是一个假想的连续空间，实际是分段连续的，

为了维护其 "整体连续" 、以及随机访问的假象，其重任落在了 deque 的迭代器身上。

因此 deque 的迭代器设计就尤为复杂，如下图所示：

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

0x02 deque 的缺陷

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

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

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

0x03 deque，stack 和 queue 的底层默认容器

在 stack 和 queue 的实现上，是选择 deque 作为底层默认容器的。

❓ 思考：为什么选择 deque 作为 stack 和 queue 的底层默认容器？

① stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以。

② queue 是先进先出的特殊线性数据结构，只要具有 push_back() 和 pop_front() 操作的线性结构，都可以作为 queue 的底层容器，比如 list 。

但 STL 最终选择用 deque 作为 stack 和 queue 的底层容器，其主要原因是如下：

stack 和 queue 不需要遍历（因此 stack 和 queue 没有迭代器），只需要在固定的一端或者两端进行操作。

在 stack 中元素增长时，deque 比 vector 的效率高（扩容时不需要搬移大量数据）；queue  中的元素增长时，deque 不仅效率高，而且内存使用率高。 结合了 deque 的优点，而完美的避开了其缺陷。

真正做到了扬长避短，可谓是神乎其技的选择！