目录
容器适配器
stack 和 queue 是 C++ 标准模板库（STL）中的容器适配器，而不是容器本身。这是因为它们并不像 vector、deque 或 list 那样直接管理元素的存储，而是基于其他底层容器来提供特定的接口功能。
简单理解就是：stack 和 queue 实际上是对其他容器（如 vector、deque 或 list）的包装，以便实现特定的操作行为。
学过数据结构后我们知道，stack（栈）可以通过顺序表或链表实现，queue（队列）同样如此。在 C++ 中，如果我们定义一个 stack 并指定使用 vector 作为底层容器，那么定义出来的 stack 就是对 vector 容器进行包装，提供了栈的操作接口（如 push、pop、top 等）。
双端队列类deque
双端队列（deque） 虽然名字中有“队列”，但实际上它更像是一个可以在两端插入数据的结构。
为了实现下标的随机访问，双端队列需要分配连续的内存空间。如果只是在连续空间中进行操作，它的行为与 vector 类似，但在插入数据时仍需要考虑是否扩容。为了解决这个问题，双端队列采用了分段内存的策略，即分配多个连续的小块内存。这些小块内存由指针维护，类似于 list 的设计。为了保证下标访问的连续性，双端队列还引入了一个中央控制数组，用于存储指向这些小块内存的指针。这样一来，就实现了既能在两端高效插入数据，又能随机访问元素的功能。设计如下图所示：
假设每个数据数组已经装满了整型数据。
在介绍了双端队列（deque）的数据头部插入和尾部插入后，接下来讨论如何使用迭代器遍历 deque。
双端队列的迭代器（此处仅讨论非 const 迭代器，const 迭代器的设计与此类似）结构设计如下：
stack的模拟实现
了解了容器适配器的概念后，stack 的模拟实现确实变得相对简单。实际上，我们只需要利用底层容器的成员函数来实现 stack 的各个接口函数即可。
具体实现代码如下：
namespace RussLeo // 防止命名冲突
{
template<class T, class Container = std::deque<T>>
class stack
{
public:
// 元素入栈
void push(const T& x)
{
_con.push_back(x); // 将元素 x 添加到容器的末尾
}
// 元素出栈
void pop()
{
_con.pop_back(); // 从容器的末尾移除最后一个元素
}
// 获取栈顶元素
T& top()
{
return _con.back(); // 返回容器末尾的元素，即栈顶元素
}
const T& top() const
{
return _con.back(); // 返回容器末尾的元素，即栈顶元素（const 版本）
}
// 获取栈中有效元素个数
size_t size() const
{
return _con.size(); // 返回容器中元素的数量
}
// 判断栈是否为空
bool empty() const
{
return _con.empty(); // 如果容器为空，则返回 true；否则返回 false
}
// 交换两个栈中的数据
void swap(stack<T, Container>& st)
{
_con.swap(st._con); // 交换当前栈和给定栈中的元素
}
private:
Container _con; // 底层容器，默认为 std::deque<T>
};
}
queue的模拟实现
在深入理解容器适配器的概念后，模拟实现队列（Queue）变得相对简单。实际上，我们只需利用底层容器的成员函数来实现队列的各个接口函数。
具体实现代码如下：
namespace RussLeo // 防止命名冲突
{
template<class T, class Container = std::deque<T>>
class queue
{
public:
// 队尾入队列
void push(const T& x)
{
_con.push_back(x); // 将元素 x 添加到容器的末尾
}
// 队头出队列
void pop()
{
_con.pop_front(); // 从容器的前端移除第一个元素
}
// 获取队头元素
T& front()
{
return _con.front(); // 返回容器前端的元素，即队头元素
}
const T& front() const
{
return _con.front(); // 返回容器前端的元素，即队头元素（const 版本）
}
// 获取队尾元素
T& back()
{
return _con.back(); // 返回容器末尾的元素，即队尾元素
}
const T& back() const
{
return _con.back(); // 返回容器末尾的元素，即队尾元素（const 版本）
}
// 获取队列中有效元素个数
size_t size() const
{
return _con.size(); // 返回容器中元素的数量
}
// 判断队列是否为空
bool empty() const
{
return _con.empty(); // 如果容器为空，则返回 true；否则返回 false
}
// 交换两个队列中的数据
void swap(queue<T, Container>& q)
{
_con.swap(q._con); // 交换当前队列和给定队列中的元素
}
private:
Container _con; // 底层容器，默认为 std::deque<T>
};
}