C++ STL 栈与队列模拟实现及容器适配器原理
前言
本文从 STL 容器适配器视角，深度解析栈与队列的设计本质——以双端队列（deque）为底层容器，实现高效头尾操作。结合最小栈、二叉树层序遍历等经典算法题，实战演示栈的"先进后出"与队列的"先进先出"特性，并揭秘优先级队列的堆实现原理。
一、栈与队列原型简介
1.1 Stack
Stack 官方文档链接： https://cplusplus.com/reference/stack/stack/?kw=stack
在 Stack 官方文档说明中介绍其不是容器而是容器适配器。在文档中栈和在 C 语言中实现的其——先进后出的特点，其使用的是模板 + 封装实现的，这里使用的缺省参数是 deque(在后面我们会介绍)，如下是栈的主要接口：
这些接口我们发现很熟悉，在 C 语言中便已经实现过了。
注意：容器适配器不再拥有迭代器了，举个简单的例子，如果栈和队列拥有了迭代器便不能保证先进先出和先进后出，而是可以通过迭代器的下标 + [] 即可出入数据。
1.2 Queue
队列官方文档链接： https://cplusplus.com/reference/queue/queue/
同理：在 Queue 官方文档说明中介绍其不是容器而是容器适配器，在文档中栈和在 C 语言中实现的其——先进先出的特点，如下是队列的主要接口：
1.3 最小栈的练习
力扣网址： https://leetcode.cn/problems/min-stack/
题目解释： 在本题中除了需要完成栈的基本接口以外，还要在时间复杂度为 O(1) 的情况下找到最小的元素。
思路： 在这道题中大部分想到的思路便是：
- 通过定义变量来存储最小的值，将第一次插入到栈的数据先存放到变量中（假设第一次插入的数据为最小值）。
- 再将后续的数据一个个插入到栈中，依次和变量存储的数据进行比较，如果插入栈中的数据小于变量存放的则变量中的数据更新为新的数据。
但是我们如果要出栈的话，存放在变量中的最小元素也要删除，那么在栈中最小的元素是什么？如果我们要遍历栈，那么时间复杂度为 O(n)。
在前面的算法中我们便知道可以定义两个栈，一个栈 _str 用来进行入栈和出栈数据的存放与删除，一个栈 _minstr 用来和 _str 中插入的数据比大小：
- 若
_str入的数据小于_minstr中的数据，那么便将该数据插入到_minstr中（第一次数据入_str的同时也要入_minstr）。 - 如果
_str插入的数据一直大于_minstr存放的数据，那么便不在_minstr中入数据（如果插入的数据与_minstr存放的数据相同是要将该数据存放到_minstr中）。
代码演示：
class MinStack {
public:
MinStack() {}
{
_str.(val);
(_minstr.() || val <= _minstr.()) {
_minstr.(val);
}
}
{
(_str.() == _minstr.()) {
_minstr.();
}
_str.();
}
{ _str.(); }
{ _minstr.(); }
:
stack<> _str;
stack<> _minstr;
};
