一、容器适配器
STL并没有将stack和queue划分为容器，而是将其称为容器适配器，原因是stack和queue只是对其他容器的接口进行了封装。
这也让stack和queue模拟实现起来异常简单，所以两个合在一起讲解介绍。
二、stack
细节：
- stack具有LIFO（后进先出）性质
- 默认容器使用vector，使用尾插尾删效率高（STL库中使用deque）
template<class T, class Container = vector<T>> class stack { public: private: Container _con; };
2.1 push
压栈
void push(const T& x) { _con.push_back(x); }
2.2 pop
出栈
void pop() { _con.pop_back(); }
2.3 top
获取栈顶元素
const T& top() const { return _con.back(); }
2.4 size
获取栈的有效元素个数
size_t size() const { return _con.size(); }
2.5 empty
判断栈是否为空
bool empty() const { return _con.empty(); }
三、queue
细节：
- queue具有FIFO（先进先出）性质
- 默认容器使用list，使用尾插头删效率高（STL库中使用deque）
template<class T, class Container = list<T>> class queue { public: private: Container _con; };
3.1 push
入队
void push(const T& x) { _con.push_back(x); }
3.2 pop
出队
void pop() { _con.pop_front(); }
3.3 front
获取队头元素
const T& front() const { return _con.front(); }
3.4 back
获取队尾元素
const T& back() const { return _con.back(); }
3.5 size
获取队列的有效元素个数
size_t size() const { return _con.size(); }
3.6 empty
判断队列是否为空
bool empty() const { return _con.empty(); }
四、deque
4.1 deque的介绍
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
4.2 deque的底层结构
其实，deque并不是一整块连续空间，而是一段一段连续的小空间结合在一起。deque有一个中控数组，存放一段段小空间的指针，类似动态开辟的二维数组。
一开始在中间开辟空间，随后根据需求向两边进行扩容。
所以，针对分段连续的空间结构，为了支持随机访问，设计出了比较复杂的迭代器。
这样的空间结构，也导致遍历的效率变得十分低下，因为deque的迭代器需要频繁判断是否抵达分段空间的边界
4.3 deque的优势与缺陷
优势：
- 支持随机访问
- 头尾的插入删除，时间复杂度为O(1)
缺陷：
- 中间插入删除比较麻烦
- 不适合遍历
总体来说，deque结合了vector和list的优势，却又没有vector和list的性能那么极致，在大部分场景下都不太常用，所以这里只是简单介绍，并不模拟实现底层结构。
4.4 为什么选择deque作为stack和queue的底层默认容器
原因有两点：
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长
时，deque不仅效率高，而且内存使用率高。
结合了deque的优点，而完美的避开了其缺陷。
总结
这次学习了容器适配器——stack和queue，了解到用容器作为模板的美妙与神奇，极大简化构建容器的代码量。同时简单了解deque的结构和使用场景，进一步理解STL容器的设计。
真诚点赞，手有余香
