C++STL——stack,queue

前言

本篇主要讲解stack与queue的底层，但并不会进行实现，stack的接口
queue的接口 ，关于stack与queue的接口在这里不做讲解，因为通过前面的对STL的学习，这些接口都是大同小异的。

容器适配器

我们可以发现，stack与queue的第二个参数都是deque。并且在STL里，stack与queue都没有被分配到容器那一分类，，而是容器适配器中。

容器适配器是一种设计模式，该种模式是将一个类的接口转换成客户希望的另外一个接口。即我们的stack与queue是对deque的接口进行了包装而已。我们在前期学习数据结构的时候，stack与queue可以通过数组和链表进行实现，那么对应到C++里面，是可以通过vector与list进行实现的，那么为什么默认使用deque进行实现呢？

deque

deque其命为双端队列，即可以在两端进行插入删除切时间复杂度为O(1)，那既然有deque，那么其是否可以取代vector与list呢？当然不行。
先进行补充CPU缓存区的概念：CPU要访问内存中的数据，需要看这个数据是否在缓冲区中，在的话就叫缓存命中，如果没有命中那么就需要先加载到缓存再进行访问缓存。读取数据根据局部性原理（如果一个数据被访问，那么它附近的数据也可能很快被访问。）是不会进行每次只读一个数据的，内存会先把一部分连续的数据读入到缓存区中的。

vector的优点:
1.vector支持随机访问。
2.CPU高速缓存命中率高。因为vector的数据地址是连续的，所以其连续的数据会在缓存区中，所以其高速缓存命中率高
vector的缺点：
1.头部与中部插入与删除数据效率低，因为要挪动数据。
2.扩容后会存在空间浪费的问题
list的优点:
1.任意位置支持O(1)的时间插入删除
2.不存在扩容，也就不会有浪费空间的问题
list的缺点:
1.不支持下标随机访问
2.CPU高速缓存命中率低，因为其内存地址是碎片的。

那么我们的deque是同时兼具两者的优点的，即支持随机访问，CPU高速缓存命中率高，头插的效率高，也没有扩容的问题与list相比其空间利用率也更高。但是deque在vector与list的优点上是比不过的，例如vector的随机访问的效率是比deque快的。
但是deque的致命缺陷就是其遍历非常困难，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
stack是一种后进先出的特殊线性数据结构，因此只要具有push_back()和pop_back()操作的线性结构，都可以作为stack的底层容器，比如vector和list都可以；queue是先进先出的特殊线性数据结构，只要具有push_back和pop_front操作的线性结构，都可以作为queue的底层容器，比如list。

那么为什么选择deque作为stack与queue的底层默认容器呢

1. stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进行操作。
2. 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的元素增长时，deque不仅效率高，而且内存使用率高