一、deque
1.1 deque的原理介绍
**deque(双端队列)：是一种双开口的“连续空间”的数据结构。**双开口的含义是：可以在头尾两端进行插入和删除操作，并且时间复杂度是O(1)的，与vector相比，头插效率高，不需要搬移元素；与list比较空间利用率高。
vector:连续的物理结构，优势：支持下标访问，劣势：扩容头部插入删除的效率低。
list:一块一块的分散结构，优势：按需申请释放任意位置插入删除的效率高，劣势：下标访问效率低，在标准库的实现中是不支持下标访问的。
以下是deque的图示：
deque并不是真正连续的空间，而是由一段断的连续的小空间拼接而成的，实际deque是类似于一个动态的二维数组的结构的，其底层结构如下图所示：
双端队列底层是一段假象的连续空间，实际上是分段连续的，为了维护其“整体连续”以及随机访问的假象，落在了deque的迭代器身上，因此deque的迭代器的实现比较复杂，如下图所示：
deque借助迭代器维持假象的连续结构的原理：
中控数组的本质就相当于一个指针数组，中控数组中的每个元素指向一个小数组，从而实现一个连续空间的假象，其实是有一段段小的连续空间通过中控数组联系起来的。
1.2 deque的缺陷
与vector比较，deque的优势是：头部插入和删除时，不用挪动元素，效率比较高，而且在扩容时也不需要挪动元素，因此效率是一定比vector高的。
与list比较 ，deque的底层是一个伪连续空间，空间利用率高，不需要存储额外字段。
致命缺陷 ：deque不适合用来遍历，因为在遍历时deque的迭代器需要频繁的检测其是否移动到某段小空间的边界，导致效率低下，但是在序列式的场景下，可能要经常进行遍历，因此在实际中对于线性结构大多数的情况下还是优先使用vector和list，deque的引用并不多，deque作为stack和queue的底层数据结构是比较好的。
二、为何选择deque作为stack和queue的默认容器
1，stack和queue是不需要进行遍历的（因此stack和queue是没有迭代器的），只需要固定的一端或者两端进行操作。
2，在stack中元素增长时，deque比vector的效率高（因为扩容时不需要进行挪动数据）；queue中的元素增长时deque不仅效率高，而且内存使用率同样也高。
对于在作为stack和queue的底层容器是正好结合了deque的优点而且完美的避开了它的缺点。
三、deque的使用
3.1 stack的模拟实现：
template<class T, class Con = deque<T>>
//栈
class stack
{
public:
//栈的构造
stack() {}
//push直接借助传入容器的push即可
void push(const T& x)
{
c.push_back(x);
}
//pop借助容器的pop将栈顶元素即数组中的最后一个元素pop掉
void pop()
{
c.pop_back();
}
//返回栈顶元素即数组的最后一个元素
T& top()
{
return c.back();
}
const T& top()const
{
return c.back();
}
//返回栈内的元素个数，直接返回容器的size即可
size_t size()const
{
return c.size();
}
//判断栈是否为空，直接判断容器是否为空即可
bool empty()const
{
return c.empty();
}
private:
Con c;
};
3.2 queue的模拟实现：
template<class T, class Con = deque<T>>
//队列
class queue
{
public:
//队列的构造
queue() {}
//进队列，先进先出，队尾进队头出，选择头插
void push(const T& x)
{
c.insert(c.begin(), x);
}
//出队列尾删即可
void pop()
{
c.pop_back();
}
//返回队尾元素，即返回容器的头
T& back()
{
return c.front();
}
const T& back()const
{
return c.front();
}
//返回队头元素，即返回容器的尾
T& front()
{
return c.back();
}
const T& front()const
{
return c.back();
}
//返回队列中的有效数据，即返回容器的size
size_t size()const
{
return c.size();
}
//判断队列是否为空，即判断容器是否为空即可
bool empty()const
{
return c.empty();
}
private:
Con c;
};
四、总结
1.deque 的结构，支持下标随机访问，偶尔使用还行，但是大量访问的效率远不及vector
2.deque的insert和erase是需要考虑挪动数据的，因此效率不高。
3.deque的头尾插入删除效率很高，STL库中的stack和queue的底层是基于deque实现的。
结论：deque作为stack和queue的底层容器是很适合的。
ector**
2.deque的insert和erase是需要考虑挪动数据的，因此效率不高。
3.deque的头尾插入删除效率很高，STL库中的stack和queue的底层是基于deque实现的。
结论：deque作为stack和queue的底层容器是很适合的。
