deque的介绍及使用

deque(double ended queue) 作为双端队列，不论在尾部或头部插入元素，都十分便捷。而在中间插入元素会比较费时，因为必须移动中间其他的元素。

双端队列是一种随机访问的数据类型，提供了在序列两端快速插入和删除的功能，它可以在需要的时候改变自身大小，完成了标准 C++ 数据结构中队列的所有功能。

deque 和 vector的差别

deque 则是一种双向开口的连续线性空间，vector是单向开口的连续线性空间。
deque 对象在队列的两端插入和删除元素比较高效，vector 在序列末尾插入和删除元素比较高效。
deque 允许在常数时间内在序列头部进行元素的插入和删除操作，并且 deque 没有所有的 capacity() 观念，它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。vector会因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间，即空间预留机制。

虽然 deque 也提供 Random Access Iterator，但它的迭代器并不是普通的指针，复杂度较高。因此除非必要，应尽可能选择使用 vector 而非 deque。对 deque 的排序操作，可以先完整复制到一个 vector 中，使用 STL 中的排序操作对 vector 排序后，再复制回 deque。

deque 通常由一些独立的区块组成，第一个区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问，但不像 vector 一样把所有对象保存在一个连续的内存块，而是多个连续的内存块，并且在一个映射结构中保存对这些块以及顺序的跟踪。

1、构造函数

#include<deque>
deque<type> deq;            //声明一个元素类型为 type 的双端队列 deq
deque<type> deq(nSize);            //声明含有 nSize 个默认初始化元素的 deq
deque<type> deq(nSize, value)            //声明含有 nSize 个值为 value 的元素的deq
deque<type> deq(MyDeque);            //复制MyDeque到deq
deque<type> deq(first, last);            //使用迭代器first，last范围内的元素初始化deq

2、常用成员函数

deq[nPos];            //访问双向序列中 nPos 位置上的元素
deq.front();            //返回第一个元素
deq.back();            //返回最后一个元素
deq.push_front(x);            //把元素 x 插入到 deq 的头部
deq.pop_front();            //弹出 deq 的第一个元素
deq.push_back(x);            //把元素 x 插入到 deq 的尾部
deq.pop_back();            //弹出 deq 的最后一个元素