从有趣的角度学习C++ STL stack&queue
小星是小明的弟弟（成分复杂），对C++方面比较感兴趣，于是想向对C++比较了解的哥哥小明学习，但是又比较懒于是就...
👨🚀小明：”小星，今天我们来学习stack&queue基础知识及其模拟实现“
🧚小星：”啊？这么长的名字，肯定很难...（虽然对C++感兴趣，但是听起来好难，好想打游戏啊）“
👨🚀小明：”有句话你在高中的时候应该听老师讲过，越长越简单，说明什么都告诉你了。“
🧚小星：”也是，但是我学完了你得和我去陪我唱歌、跳舞、Rap、打篮球（好像有点道理，那就学吧，但是得耍点坏）“
👨🚀小明：”呃，怎么感觉有点不对呢（暗地里：呵呵），算了，答应你，在讲stack&queue之前，先由我给你简单了解一下容器适配器。”
🧚小星：“好耶（坏），但是什么是容器适配器？（疑惑）”
📍容器适配器
🎈什么是适配器？
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
可以这样理解：
我们生活中经常需要用到插口转换器，比如现在很多手机都只有一个插口，这个口可以直接用来充电和听音乐。但是前提是我们使用的充电器和耳机的插口要和这个设备适配的。
目前市面上很多手机的插口都是Type-C或者Lightning型号：但是，我们常用的耳机型号却是2.5mm和3.5mm的圆形接口。
所以，当我们想要把自己的3.5mm圆形接口的耳机插入Lightning或者Type-C接口的时候，就需要一个转换器。
同理，在软件系统中，常常要将一些"现存的对象"放到新的环境中，而新环境要求的接口是现对象不能满足。如以下类似的场景：
✨1、系统需要使用现有的类，而此类的接口不符合系统的需要。
✨2、想要建立一个可以重复使用的类，用于与一些彼此之间没有太大关联的一些类，包括一些可能在将来引进的类一起工作，这些源类不一定有一致的接口。
✨3、通过接口转换，将一个类插入另一个类系中。（比如老虎和飞禽，现在多了一个飞虎，在不增加实体的需求下，增加一个适配器，在里面包容一个虎对象，实现飞的接口。）
👨🚀小明：“适配器就不展开讲了，只需要对它有个概念就好。听懂了嘛”
🧚小星：“听懂了，就是说我们上面要实现的功能是一样的，比如说给typec接口的手机充电，但是因为充电器线带错了，接口的不同需要连接一个转换器来让它变成typec的接口来给手机充电。”
👨🚀小明：“可以可以，有点东西，接下来简单讲一下STL标准库中stack和queue的底层结构”
🧚小星：“放马过来吧（傲娇脸）”
🎈STL标准库中stack和queue的底层结构
👨🚀小明：“虽然
stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque，我们可以在这个网站上查到：cplusplus.com - The C++ Resources Network”比如：
🎈deque的简单介绍(了解)
👨🚀小明：“再介绍一下deque”
📌deque的原理介绍
✨deque(双端队列)：是一种
双开口的"连续"空间的数据结构✨双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)
✨与
vector比较，头插效率高，不需要搬移元素✨与
list比较，空间利用率比较高
✨deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：
✨双端队列底层是一段
假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：
🧚小星：“那deque是如何借助其迭代器维护其假想连续的结构呢？”
👨🚀小明：“为了实现deque的迭代器，deque采用了一个chunk大小的策略，即将容器等分成多个chunk（块），每个chunk内部是连续的一段空间，但是chunk之间并不连续。
deque的迭代器会维护一个指向当前chunk的指针，以及当前指针所在的块内的元素迭代器。
当进行迭代器的移动操作时，如果需要跨过chunk的边界，则会重新指向下一个或上一个chunk的起始位置，并更新当前指针所在的块内的元素迭代器。
这样，虽然deque内部的存储并不是连续的，但是通过迭代器的维护，可以实现高效的遍历、插入和删除操作，同时维护其假想连续的结构。如下图所示：”
🧚小星：”哦哦明白了，就是一个逻辑上的大大的数组，但是实际上是用指针来指向不同的块，如果要找的元素在上一块上就要去找上一块的起始位置，然后往后按顺序找，但是这样不会效率很低吗？总是要在不同的块上找...“
👨🚀小明(惊讶)：“没错没错，这都让你发现了，但是这正是我们接下来要讲的--deque的缺陷”
📌deque的缺陷
👨🚀小明：“
✨与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
✨与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
✨但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
”
🧚小星：“哦~高不成低不就呗，但是为什么要将它作为stack和queue的底层数据结构啊？它不是效率低吗？”（大写的问号）
👨🚀小明（邪魅一笑）：“还挺警觉，是这样的...👇”
🎈为什么选择deque作为stack和queue的底层默认容器？
✨stack是一种后进先出的特殊线性数据结构，因此**只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，**比如
vector和list都可以；✨queue是先进先出的特殊线性数据结构，**只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，**比如
list。✨但是STL中对
stack和queue默认选择deque作为其底层容器，主要是因为：**stack和queue不需要遍历(**因此 stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。结合了deque的优点，而完美的避开了其缺陷。
🧚小星：“哦哦懂了，早说嘛~，你之前又没说stack和queue是什么(心想可恶就知道卖弄)”
👨🚀小明：“好了好了，正经教了，接下来就要介绍stack&queue的概念和使用了，坐好发车了~”
📍stack的介绍和使用
🎈stack的介绍
👨🚀小明：“这里我们先看一下文档是怎么说的。总结就是下面几点。”
stack文档
✨
stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。✨
stack是作为容器适配器被实现的，这里在前情提要里讲过了，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。✨
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
✨标准容器 vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。
👨🚀小明给小星展示了一张表“它的常用函数有下面这些，每一个都是链接了文档的超链接，想了解更多就点它，后面接口说明有功能介绍”
🎈stack的常用函数
✨函数说明 ✨接口说明 ✨stack() ✨构造空的栈 ✨empty() ✨检测stack是否为空 ✨size() ✨返回stack中元素的个数 ✨top() ✨返回栈顶元素的引用 ✨push() ✨将元素val压入stack中 ✨pop() ✨将stack中尾部的元素弹出
🎈stack的使用
👨🚀小明：“在前面介绍了函数的功能，是不是觉得很简单？（又想考验小星了）”
🧚小星：“就这？我幼儿园都能学会（叉腰）”
👨🚀小明：“好，那我就给你出几道题，你做做（呵，鱼儿上钩了）”
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.提示：
-2^31^
