C++：模拟stack、queue
目录
容器适配器
定义
特点
deque
deque的优势与缺点
选择deque作为stack和queue的底层默认容器的原因
模拟实现stack
模拟实现queue
容器适配器
定义
在C++标准模板库（STL）中，容器适配器（Container Adapters）是一种特殊的容器，它们没有自己的数据结构，而是对现有容器（string、vector、list、deque等）的接口进行封装，从而提供不同功能的接口。
容器适配器通常用来提供与标准容器不同的接口，或者提供额外的功能。
常用的容器适配器
1.栈（stack）
- 提供先进先出（LIFO）的数据结构。
- 通常基于deque、list或vector实现。
- 提供 push()、
pop()、top()和empty()等操作。
2.队列（queue）
- 提供先进先出（FIFO）的数据结构。
- 通常基于
deque或list实现。 - 提供
push()、pop()、front()、back()和empty()等操作。
3.优先队列（priority_queue）
- 提供一个最大值总是在顶部的队列（其实就是堆，默认情况是大堆）。
- 通常基于
vector实现，使用堆排序。 - 提供
push()、pop()、top()和empty()等操作。
特点
- 轻量级：容器适配器不包含复杂的数据结构，它们通常只包含一个指向底层容器的指针。
- 易用性：容器适配器提供简单直观的接口，易于理解和使用。
- 灵活性：可以通过改变底层容器的类型来调整容器适配器的性能和功能。
- 可扩展性：用户可以自定义比较函数或分配器，以适应特定的需求。
deque
标准模板库里stack和queue是对deque进行封装的，所以我们先来认识下deque。
deque其实就是双端队列，是一种双开口“连续”空间的数据结构，它提供了在队列的两端快速插入和删除元素的能力，其时间复杂度为O(1)。
关键特性
1.deque的大小可以动态变化，根据需要自动调整。
2.支持随机访问
3.在两端进行操作，提供
push_front()、push_back()和pop_front()、pop_back()操作。4.内存效率比vector高，因为可以在两端分配不同大小的内存块，减少空间浪费。
5.提供了迭代器，允许使用迭代器遍历容器中的元素。
deque其实并不是真正的连续空间，而是由一段段连续的小空间拼接而成，类似于一个动态的二维数组。
双端队列是一段特殊的连续空间，它不是真正连续的，实际上是分段连续的，为了维护其“整体连续”以及随机访问，就落在了deque的迭代器上，它的设计比较复杂。
deque的优势与缺点
与vector比较，deque的优势是，头部插入删除时，不需要移动元素，效率高，扩容时也不需要搬移大量元素，总的来说效率要比vector高。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
deque的缺陷，不适合遍历，因为在遍历时，deque的迭代器要频繁检查其是否移动到小空间的边界，效率低下。实际上，需要线性结构时，大多数情况优先考虑vector和list，deque的应用不多，其中一个就是，STL将其作为stack和queue的底层数据结构。
选择deque作为stack和queue的底层默认容器的原因
1.stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高。
简单来说，deque作为底层默认容器结合了其优点而又完美避开了其缺陷，所以我们模拟实现迭代器使用deque作为其底层容器。
模拟实现stack
template<class T, class Container = deque<T>>
class stack
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}int size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;
};模拟实现queue
template<class T, class Container = deque<T>>
class queue
{
public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}int size() const{return _con.size();}bool empty() const{return _con.empty();}private:Container _con;
};拜拜，下期再见😏
摸鱼ing😴✨🎞
