所谓的deque是”double ended queue”的缩写，双端队列不论在尾部或头部插入元素，都十分迅速。而在中间插入元素则会比较费时，因为必须移动中间其他的元素。双端队列是一种随机访问的数据类型，提供了在序列两端快速插入和删除操作的功能，它可以在需要的时候改变自身大小，完成了标准的C++数据结构中队列的所有功能。
Vector是单向开口的连续线性空间，deque则是一种双向开口的连续线性空间。deque对象在队列的两端放置元素和删除元素是高效的，而向量vector只是在插入序列的末尾时操作才是高效的。deque和vector的最大差异，一在于deque允许于常数时间内对头端进行元素的插入或移除操作，二在于deque没有所谓的capacity观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque中是不会发生的。也因此，deque没有必要提供所谓的空间预留（reserved）功能。
虽然deque也提供Random Access Iterator，但它的迭代器并不是普通指针，其复杂度和vector不可同日而语，这当然涉及到各个运算层面。因此，除非必要，我们应尽可能选择使用vector而非deque。对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，将vector排序后（利用STL的sort算法），再复制回deque。
deque是一种优化了的对序列两端元素进行添加和删除操作的基本序列容器。通常由一些独立的区块组成，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。它允许较为快速地随机访问但它不像vector一样把所有对象保存在一个连续的内存块，而是多个连续的内存块。并且在一个映射结构中保存对这些块以及顺序的跟踪。

1、声明deque容器

#include<deque>  // 头文件
deque<type> deq;  // 声明一个元素类型为type的双端队列que
deque<type> deq(size);  // 声明一个类型为type、含有size个默认值初始化元素的的双端队列que
deque<type> deq(size, value);  // 声明一个元素类型为type、含有size个value元素的双端队列que
deque<type> deq(mydeque);  // deq是mydeque的一个副本
deque<type> deq(first, last);  // 使用迭代器first、last范围内的元素初始化deq

2 deque的常用成员函数

deq[ ]：                访问双向队列中单个的元素。
deq.front()：        返回第一个元素的引用。
deq.back()：            返回最后一个元素的引用。
deq.push_front(x)：    把元素x插入到双向队列的头部。
deq.pop_front()：    弹出双向队列的第一个元素。
deq.push_back(x)：    把元素x插入到双向队列的尾部。
deq.pop_back()：        弹出双向队列的最后一个元素。

3.2.3 deque的一些特点

1. 支持随机访问，即支持[ ]以及at()，但是性能没有vector好。
2. 可以在内部进行插入和删除操作，但性能不及list。
3. deque两端都能够快速插入和删除元素，而vector只能在尾端进行。
4. deque的元素存取和迭代器操作会稍微慢一些，因为deque的内部结构会多一个间接过程。
5. deque迭代器是特殊的智能指针，而不是一般指针，它需要在不同的区块之间跳转。
6. deque可以包含更多的元素，其max_size可能更大，因为不止使用一块内存。
7. deque不支持对容量和内存分配时机的控制。
8. 在除了首尾两端的其他地方插入和删除元素，都将会导致指向deque元素的任何pointers、references、iterators失效。不过，deque的内存重分配优于vector，因为其内部结构显示不需要复制所有元素。
9. deque的内存区块不再被使用时，会被释放，deque的内存大小是可缩减的。不过，是不是这么做以及怎么做由实际操作版本定义。
10. deque不提供容量操作：capacity()和reverse()，但是vector可以。

    #include<iostream>
    #include<stdio.h>
    #include<deque>
    using namespace std;
    int main(void)
    {
     int i;
     int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
     deque<int> q;
     for (i = 0; i <= 9; i++)
     {
         if (i % 2 == 0)
             q.push_front(a[i]);
         else
             q.push_back(a[i]);
     }                                  /*此时队列里的内容是: {8,6,4,2,0,1,3,5,7,9}*/
     q.pop_front();
     printf("%d\n", q.front());    /*清除第一个元素后输出第一个(6)*/
     q.pop_back();
     printf("%d\n", q.back());     /*清除最后一个元素后输出最后一个(7)*/
     deque<int>::iterator it;
     for (it = q.begin(); it != q.end(); it++) {
         cout << *it << '\t';
     }
     cout << endl;
     system("pause");
     return 0;
    }
    

黑马学习笔记

1、deque容器基本概念：
功能：
双端数组，可以对头和尾进行插入删除操作
deque与vector的区别：
vector对于头部插入删除效率低，数据量越大，效率越低
deque相对而言，头部插入删除速度快
vector访问元素时的速度会比deque快，这和者内部实现有关
deque容器的迭代器也支持随机访问
deque容器图解：

#include<iostream>
using namespace std;
#include<deque>

//构造函数（和vector容器基本一致）
/*
    deque<T> d;默认构造函数
    deque(beg,end);构造函数将[beg,end]区间中的元素拷贝给本身
    deque(n,elem);构造函数将n个elem拷贝给本身
    deque(const deque &deq);拷贝构造函数

*/
void PrintDeque(deque<int>& D)
{
    for (deque<int>::iterator it = D.begin(); it != D.end(); it++)//iterator普通迭代器
    {
        *it = 100;//这里可以修改容器中所存在的数据
        cout << *it << " ";
    }
    cout << endl;
}
void ConstPrintDeque(const deque<int> D)//只读迭代器
{
    for (deque<int>::const_iterator it = D.begin(); it != D.end(); it++)//const_iterator静态迭代器
    {
        //*it = 100;容器中的数据将不能改变
        cout << *it << " ";
    }
    cout << endl;
}

int main()
{
    deque<int> d1;    //deque<T> d;默认构造函数
    for (int i = 0; i < 10; i++)
    {
        d1.push_back(i + 1);
    }
    ConstPrintDeque(d1);//1 2 3 4 5 6 7 8 9 10
    //PrintDeque(d1);//100 100 100 100 100 100 100 100 100 100

    deque<int> d2(d1.begin(), d1.end());//deque(beg,end);构造函数将[beg,end]区间中的元素拷贝给本身
    ConstPrintDeque(d2);//1 2 3 4 5 6 7 8 9 10

    //deque(n,elem);构造函数将n个elem拷贝给本身
    deque<int> d3(5,100);//5个100
    ConstPrintDeque(d3);//100 100 100 100 100

    deque<int> d4(d1);//deque(const deque &deq);拷贝构造函数
    ConstPrintDeque(d4);//1 2 3 4 5 6 7 8 9 10
    return 0;
}

#include<iostream>
using namespace std;
#include<deque>

//赋值函数
/*
函数原型：
    deque& operator=(const deque& d);重载等号赋值操作
    assign(beg,end);//将[beg,end]之间的数拷贝给本身
    assign(n,elem);//将n个elem拷贝给自身
*/
void ConstPrintQeque(const deque<int>& D)
{
    for (deque<int>::const_iterator it = D.begin(); it != D.end(); it++)
        cout << *it << " ";
    cout << endl;
}

int main()
{
    deque<int> d1;//默认构造函数
    for (int i = 0; i < 10; i++)
        d1.push_back(i + 1);

    //deque& operator=(const deque & d); 重载等号赋值操作
    deque<int>d2;
    d2 = d1;
    ConstPrintQeque(d1);

    //assign(beg, end);//将[beg,end]之间的数拷贝给本身
    deque<int>d3;
    d3.assign(d1.begin(), d1.end());
    ConstPrintQeque(d3);

    //assign(n, elem);//将n个elem拷贝给自身
    deque<int>d4;
    d4.assign(5, 10);
    ConstPrintQeque(d4);

    return 0;
}

#include<iostream>
using namespace std;
#include<deque>

//对deque容器大小进行操作
/*
    deque.empty();判断是否为空
    deque.size();返回元素个数
    deque.resize(num);重新指定容器大小为num;如果变长则以默认数字填充、变短则删除多余部分
    deque.resize(num，elem);重新指定容器大小为num;如果变长则以elem填充、变短则删除多余部分
*/
void ConstPrintDeque(const deque<int>& D)
{
    for (deque<int>::const_iterator it = D.begin(); it != D.end(); it++)
        cout << *it << " ";
    cout << endl;
}
int main(){
    deque<int>d1;
    if (d1.empty())//deque.empty();判断是否为空,空返回1
        cout << "d1容器为空" << endl;
    else
        ConstPrintDeque(d1);

    for (int i = 0; i < 10; i++)
        d1.push_back(i + 1);
    if (d1.empty())
        cout << "d1容器为空" << endl;
    else
    {
        cout << "d1的大小为：" << d1.size() << endl;
        ConstPrintDeque(d1);
    }
    cout << "重新指定容器大小\n";
    //deque.resize(num); 重新指定容器大小为num; 如果变长则以默认数字填充、变短则删除多余部分
    d1.resize(5);     
    ConstPrintDeque(d1);//1 2 3 4 5
    d1.resize(10);
    ConstPrintDeque(d1);//1 2 3 4 5 0 0 0 0 0
    //deque.resize(num，elem); 重新指定容器大小为num; 如果变长则以elem填充、变短则删除多余部分
    d1.resize(15,5);
    ConstPrintDeque(d1);//1 2 3 4 5 0 0 0 0 0 5 5 5 5 5
    return 0;
}

#include<iostream>
using namespace std;
#include<deque>

//deque_容器__插入删除
/*
两端插入删除操作：
    push_back(elem);尾插
    push_front(elem);头插
    pop_back();尾删
    pop_front();头删

指定位置插入删除：
    insert(pos,elem);在pos处插入elem,返回新插入数据位置
    insert(pos,n,elem);在pos处插入n个elem，无返回值
    insert(pos,beg,end);在pos处插入[beg,end]区间内的数据，无返回值
    erase(pos);删除pos位置的数据，返回下一个数据位置
    erase(beg,end);删除[beg,end]之间的数据，返回下一个数据的位置
    clear();清除所有数据
*/
void ConstPrintDeque(const deque<int>& d)
{
    for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
        cout << *it << " ";
    cout << endl;
}
void test01()//两端插入删除操作
{
    deque<int> d1;
    //push_back(elem); 尾插
    d1.push_back(10);
    d1.push_back(20);
    ConstPrintDeque(d1);//10 20
    //push_front(elem); 头插
    d1.push_front(100);
    d1.push_front(1000);
    ConstPrintDeque(d1);//1000 100 10 20
    //pop_back(); 尾删
    d1.pop_back();
    ConstPrintDeque(d1);//1000 100 10
    //pop_front(); 头删
    d1.pop_front();
    ConstPrintDeque(d1);//100 10
}
void test02()//指定位置进行插入删除操作
{
    deque<int>d1;
    for (int i = 0; i < 10; i++)
        d1.push_back(i + 1);
    cout << "d1:";
    ConstPrintDeque(d1);//1 2 3 4 5 6 7 8 9 10

    deque<int>d2;
    for (int i = 0; i < 5; i++)
        d2.push_back(1000);

    //insert(pos, elem); 在pos处插入elem, 返回新插入数据位置
    d1.insert(d1.begin()+1, 10);
    ConstPrintDeque(d1);//1 10 2 3 4 5 6 7 8 9 10

    //insert(pos, n, elem); 在pos处插入n个elem，无返回值
    d1.insert(d1.begin(),5, 100);
    ConstPrintDeque(d1);//100 100 100 100 100 1 10 2 3 4 5 6 7 8 9 10

    deque<int>::iterator it = d1.begin();

    //insert(pos, beg, end); 在pos处插入[beg, end]区间内的数据，无返回值
    d1.insert(++it, d2.begin(), d2.end());
    ConstPrintDeque(d1);
    //100 1000 1000 1000 1000 1000 100 100 100 100 1 10 2 3 4 5 6 7 8 9 10

    //erase(pos); 删除pos位置的数据，返回下一个数据位置
    d1.erase(d1.begin());
    ConstPrintDeque(d1);
    //1000 1000 1000 1000 1000 100 100 100 100 1 10 2 3 4 5 6 7 8 9 10

    //erase(beg, end); 删除[beg, end]之间的数据，返回下一个数据的位置
    /*d1.erase(d1.begin(), d1.end());
    cout << "-----\n";
    ConstPrintDeque(d1);*/
    //清楚首到尾的数据、相当于清空

    //clear(); 清除所有数据
    cout << "-----\n";
    ConstPrintDeque(d1);
    d1.clear();//清空数据
    ConstPrintDeque(d1);
}

int main()
{
    test01();
    test02();
    return 0;
}

#include<iostream>
using namespace std;
#include<deque>
//deque_容器_数据存取
/*
函数原型：
    operator[];重载[]
    at(int idx);返回索引idx所指向的数据
    front();返回第一个数据元素
    back();返回最后一个数据元素
*/

int main()
{
    deque<int>d1;
    for (int i = 0; i < 10; i++)//初始化
        d1.push_back(i + 1);

    for (int i = 0; i < d1.size(); i++)
        cout << d1[i] << " ";        //重载[]
    cout << endl;

    for (int i = 0; i < d1.size(); i++)
        cout << d1.at(i) << " ";    //at(int idx);返回索引idx所指向的数据
    cout << endl;

    cout << "d1的首元素：" << d1.front() << endl;
    cout << "d1的末尾元素：" << d1.back() << endl;
    return 0;
}

#include<iostream>
using namespace std;
#include<deque>
#include<algorithm>//标准算法头文件
//deque_容器_排序
/*
函数原型：
    sort(iterator beg,iterator end);对区间[beg,end]之间进行排序、默认为升序
    对于所有支持随机访问的迭代器的容器，都可以使用sort进行排序：vector、deque
*/
void ConstPrintDeque(const deque<int>& D)
{
    for (int i = 0; i < D.size(); i++)
    {
        cout << D[i] << " ";
    }
    cout << endl;
}
int main()
{
    deque<int>d;
    for (int i = 0; i < 10; i++)
    {
        d.push_back(i + 1);
        d.push_front(100 * (i+1));
    }
    ConstPrintDeque(d);//1000 900 800 700 600 500 400 300 200 100 1 2 3 4 5 6 7 8 9 10
    cout << "排序后：\n";
    sort(d.begin(), d.end());//#include<algorithm>标准算法头文件
    ConstPrintDeque(d);//1 2 3 4 5 6 7 8 9 10 100 200 300 400 500 600 700 800 900 1000

    return 0;
}