远方有一堆篝火，在为久候之人燃烧！
文章目录
一、容器适配器二、stack2.1 push2.2 pop2.3 top2.4 size2.5 empty 三、queue3.1 push3.2 pop3.3 front3.4 back3.5 size3.6 empty 四、deque4.1 deque的介绍4.2 deque的底层结构4.3 deque的优势与缺陷4.4 为什么选择deque作为stack和queue的底层默认容器 总结
一、容器适配器
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容器的设计。
