概念
Deque（双向队列）
- 和Queue差不多 ,但是特殊的是Deque可是扩充内存。（实际上连续内存的容器不能随意扩充，所以Deque也不是真正意义上的扩充内存，而是封装了底层的表象。
- Deque是由一段段构成的，当走到尾端时自动跳到下一段，（支持迭代器++操作）。
- 每次扩充，就会申请一个段，从而实现了内存连续的假象。
默认的stack 和 queue 都基于 deque 容器实现， priority_queue 则基于 vector 容器实现。
对于给定的适配器，其关联的容器必须满足一定的约束条件。
- stack 适配器所关联的基础容器可以是任意一种顺序容器类型。因此，stack 栈可以建立在vector、list 或者 deque 容器之上。
- queue 适配器要求其关联的基础容器必须提供 push_front 运算，因此只能建立在 list 或deque容器上，而不能建立在vector 容器上。
- priority_queue 适配器要求提供随机访问功能，因此可建立在vector 或 deque 容器上，但不能建立在 list 容器上。
特性
- deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
- deque 容器也可以根据需要修改自身的容量和大小。
缺点：频繁的插入删除时候，Deque并不适合。- Deque采用分块线型结构存储数据，两个迭代器分别指向首尾元素，而且拥有具有高效的push_back(),push_front()函数。 正因如此，所以Deque不易实现capacity和reverse函数。
头文件
模板
deque 容器以模板类 deque（T 为存储元素的类型）的形式在 头文件中，并位于 std 命名空间中。
set初始化方法
1
2
3
4
5
6
7
| int num[] = {1,2,3,4,5,6};
deque<int> di{1,2,3,4,5};
deque<int>q; 创建一个空双向队列 deque<T> deqT;默认构造形式
deque<int>p(5); 创建一个具有5个成员的双向队列
deque<int>s(5,1); 创建一个具有5个成员且初始值为1的双向队列 deque(n, elem);构造函数将n个elem拷贝给本身
deque<int>s2(s); 创建一个双向队列s2，并拷贝s中所有成员 deque(const deque &deq);拷贝构造函数。
deque<int>n(num,num+5); 创建一个双向队列n，并拷贝num至num+5中元素入队 deque(beg, end);构造函数将[beg, end)区间中的元素拷贝给本身。
|
交换
swap(deque<T>& other)：和参数的元素进行交换，所包含对象的类型必须相同。：将当前 deque 中的元素和参数 deque 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。
1
2
| void swap(deque<T> &x) 重载1：x.swap(y)
void swap(deque<T> &x, deque<T> &y) 重载2: swap(x, y)
|
常用操作
插入操作
1
2
3
| q.push_front(a); 头部入队
q.push_back(b); 尾部入队
q.insert(iter,x); 在iter位置插入x，iter为迭代器
|
覆盖
1
2
| q.assign(n,x); 将n个x赋值到deque中，并清空deque容器之前的内容。
q.assign(iter1,iter2); 将区间[iter1，iter2)内元素赋值给deque，并清空deque容器之前的内容。
|
删除与清空操作
1
2
3
4
5
| q.pop_front(); 头部出队
q.pop_back(); 尾部出队
q.clear(); 清空双向队列
q.erase(iter); 删除iter元素，iter为迭代器
q.erase(beg,end);删除[beg,end)区间的数据，返回下一个数据的位置。
|
deque数据存取
1
2
3
4
| q.front(); 返回头成员
q.back(); 返回尾元素
q.at(idx); 返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[]; 返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
|
大小/是否为空
1
2
3
| q.size(); 返回双向队列成员个数
q.max_size(); 返回系统支持成员最大个数
q.empty(); 判断双向队列是否为空
|
迭代器
1
2
3
4
5
6
7
8
| q.begin(); 返回头部迭代器
q.end(); 返回尾部迭代器
q.rbegin(); 返回尾部反向迭代器
q.rend(); 返回头部反向迭代器
q.cbegin(); 和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
q.cend(); 和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
q.crbegin();和rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
q.crend(); 和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。
|
参考资料
C++ STL deque容器底层实现原理（深度剖析）
STL教程：C++ STL快速入门（非常详细）
[C++ STL]deque使用详解
C++ deque的用法与示例//解释的图片不错
《C++Primer》第九章-顺序容器-学习笔记(3)-容器适配器&栈&队列
