从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(上）：https://developer.aliyun.com/article/1521883
3. deque的介绍(了解)
deque ：双端队列 - double ended queue
可以发现它的接口很多，有[ ] 也有头删。
deque 是一种双开口的 "连续" 空间的数据结构，
deque 可以在头尾两端进行插入和删除操作。且时间复杂度为O（1），
与 vector 相比，头插效率高，不需要搬移元素，与 list 相比，deque 的空间利用率更高。
3.1 deque的实现原理
deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。
实际的 deque 类似于一个动态的二维数组，其底层结构如下所示：
双端队列底层是一个假想的连续空间，实际是分段连续的，
为了维护其 "整体连续" 、以及随机访问的假象，其重任落在了 deque 的迭代器身上。
因此 deque 的迭代器设计就尤为复杂，如下图所示：
那 deque 是如何借助其他迭代器维护其假想连续的结构的呢？
3.2 deque的缺陷和使用场景
deque 有点像 vector 和 list ，我们把 vector 和 list 也拉出来进行优缺点的对比再合适不过了：
那什么场景适合用 deque 呢？
虽然不够极致但是还是有用武之地的：大量头尾插入删除，偶尔随机访问的情况可以使用 deque。
前面说到：在 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 的优点，而完美的避开了其缺陷。
4.1 priority_queue的介绍
priority_queue的底层就是以前数据结构学的堆：
数据结构与算法⑪(第四章_中)堆的分步构建_GR C的博客-CSDN博客
https://cplusplus.com/reference/queue/priority_queue/
优先队列是一种容器适配器，根据严格的弱排序标准，
它的第一个元素总是它所包含的元素中最大的。
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素
（优先队列中位于顶部的元素）。
优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，
queue提供一组特 定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，
其称为优先队列的顶部。
标准容器类 vector 和 deque 满足这些需求。默认情况下，
如果没有为特定的 priority_queue 类实例化指 定容器类，则使用 vector。
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作。
底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。
容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)（下）：https://developer.aliyun.com/article/1521890?spm=a2c6h.13148508.setting.24.712b4f0eDngT44
