极客教程C++ STL 中Deque 与 Vector 对比
Deque在C++标准模板库（STL）中
双端队列是一种序列容器，既能从两端扩展和收缩，也能在两端插入和删除第一个元素。
它们类似于向量，但支持以O(1)的时间复杂度插入和删除第一个元素。与向量不同的是，它们不能保证连续存储分配。
双端队列基本上是数据结构双端队列的一个实现。队列数据结构只允许从尾部插入和从头部删除。这就像现实生活中的队列，人们会从前面删除，从后面添加。双端队列是队列的一种特殊情况，其中插入和删除操作在两端都可以执行。
双端队列的函数与向量相同，并增加了对前后两端的push和pop操作。
向量在C++ STL中
向量与动态数组相同，能够在元素插入或删除时自动调整大小，它们的存储由容器自动处理。向量元素放置在连续存储中，因此可以使用迭代器访问和遍历。在向量中，数据插入到末尾。在末尾插入需要不同的时间，因为有时候可能需要扩展数组。删除最后一个元素只需要常数时间，因为没有调整大小。在开头或中间插入和删除是线性的。
Deque和Vector的区别：
| 向量 | 双端队列 |
|---|---|
| 提供中间和末尾的插入和删除方法 | 提供开始、中间和末尾的插入和删除方法 |
| 在开头插入和删除的性能不佳 | 在开头插入和删除具有良好的性能 |
| 存储元素连续 | 它包含存储元素连续的内存块列表 |
| 在末尾添加和删除元素的性能良好 | 在末尾添加和删除元素的性能良好 |
在C++中，存储在<vector>头文件中 |
在C++中，存储在<deque>头文件中 |
| 在前面或中间插入的时间复杂度为O(N) | 在前面和末尾插入的时间复杂度为O(1) |
| 删除的时间复杂度为O(N) | 删除的时间复杂度为O(1) |
何时选择Deque而不是Vector？
我们必须在操作的开始和末尾添加和删除元素时选择Deque(双端队列ADT)。