这篇文章介绍一下STL中队列deque的基本使用方法。
 
 


 
目录
 
双向队列deque
头文件和命名空间
常用的成员函数
代码使用示例
示例执行结果
总结

 
 
双向队列deque
 
 
 
双向队列也是队列，是最为常见的一种数据结构，双向队列在STL中有deque的实现。包含双向队列在内，队列中的元素满足FIFO（先进先出）。主要特点如下：
 
 
 
元素需满足FIFO：First In First Out
 
 
出口端称为队头（Front），入口端称为队尾（Rear）
 
 
可以使用数组或者链表来存储数据
 
 
操作主要有入队（Enqueue）和出队（Dequeue）
 
 
可以根据需要实现循环队列或者双向队列
 
 
只能在队尾插入数据，在队头删除数据
 
 
关于队列的说明内容可参看：https://blog.csdn.net/liumiaocn/article/details/108091698
 
 
头文件和命名空间
 
 
 
#include <deque>
 using namespace std;
 
 
常用的成员函数
 
queue函数名
用途
功能说明
时间复杂度
size()
查询遍历
获取元素个数
O(1)
begin()
查询遍历
获取指向第一个元素的迭代器
O(1)
end()
查询遍历
获取指向最后一个元素的迭代器
O(1)
front()
查询遍历
获取指向第一个元素的迭代器
O(1)
back()
查询遍历
获取指向最后已给元素的迭代器
O(1)
push_back
插入
在末尾插入数据x
O(1)
pop_back
删除
删除最后一个元素
O(1)
push_front
插入
在末尾插入数据x
O(1)
pop_front
删除
删除最后一个元素
O(1)
empty
删除
删除所有元素
O(n)
 
 
注：deque的成员函数主要包括插入和删除，实际对应着队列操作的入队和出队两个操作，然后就是获取元素个数和对头元素的操作，都是负载度为O (1)的操作。和stack相比，上述5个函数的函数名只是front和top有区别，其他函数名一致。
 
 
 
代码使用示例
 
#include <iostream>
#include <deque>
using namespace std;

void print_element(deque <char> q) {
    if (!q.empty()) {
        cout << "Size:" << q.size() << " Queue Top Element : " << q.back()  << " Queue:";
    } else {
        cout << "Size:" << q.size() << endl;
    }

    deque<char>::iterator it = q.begin();
    while(it != q.end()) cout << *it++;
    cout << endl;
}

int main() {
    deque <char> q;

    cout << "Queue Element In " << endl;
    print_element(q);
    q.push_back('L');
    print_element(q);
    q.push_back('i');
    print_element(q);
    q.push_back('u');
    print_element(q);

    cout << endl << "Queue Element Out " << endl;
    q.pop_back();
    print_element(q);
    q.pop_back();
    print_element(q);
    q.clear();
    print_element(q);

    q.push_back('i');
    print_element(q);
    q.push_front('L');
    print_element(q);
    q.push_back('u');
    print_element(q);
    q.pop_back();
    print_element(q);
    q.pop_front();
    print_element(q);
    q.pop_front();
    print_element(q);
}
 
示例执行结果
 
Queue Element In 
Size:0

Size:1 Queue Top Element : L Queue:L
Size:2 Queue Top Element : i Queue:Li
Size:3 Queue Top Element : u Queue:Liu

Queue Element Out 
Size:2 Queue Top Element : i Queue:Li
Size:1 Queue Top Element : L Queue:L
Size:0

Size:1 Queue Top Element : i Queue:i
Size:2 Queue Top Element : i Queue:Li
Size:3 Queue Top Element : u Queue:Liu
Size:2 Queue Top Element : i Queue:Li
Size:1 Queue Top Element : i Queue:i
Size:0
 
总结
 
变长支持、泛化类型、常用功能函数内嵌、可以使用其他多种STL的函数、使用简单，而且也支持迭代器等，都是deque被使用的原因。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
using namespace std;
int main()
{
    deque<int> d;
    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    d.push_front(10);
    d.push_front(20);
    cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<" "<<d[3]<<" "<<d[4]<<endl;//书上有误，从前面插入并不覆盖，就是从前面插队了。
    d.insert(d.begin()+1,88);
    cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
    for(int i=0;i<d.size();i++)//以数组的方式输出。
    {
        cout<<d[i]<<" ";
    }
    cout<<endl;
    deque<int>::iterator it;
    for(it=d.begin();it!=d.end();it++)//以迭代器的方式便利。
    {
        cout<<*it<<endl;
    }
    deque<int>::reverse_iterator rit;
    for(rit=d.rbegin();rit!=d.rend();rit++)//反转一下；
    {
        cout<<*rit<<" ";
    }
    cout<<endl;
   /* while(!d.empty())
    {
        cout<<d.front()<<" ";//输出头部
        d.pop_front();//从头部删除。
    }
     while(!d.empty())
    {
        cout<<d.back()<<" ";//输出尾部。
        d.pop_back();//从尾部删除。
    }*/
    d.erase(d.begin()+1);//删除从0开始第一个位置。
     for(it=d.begin();it!=d.end();it++)//以迭代器的方式便利。
    {
        cout<<*it<<endl;
    }
    d.clear();//全请空；
    cout<<d.size();
   return 0;
}

deque 也是顺序容器的一种，同时也是一个可变长数组。要使用 deque，需要包含头文件 deque。所有适用于 vector 的操作都适用于 deque。
 
deque 和 vector 有很多类似的地方。在 deque 中，随机存取任何元素都能在常数时间内完成。它相比于 vector 的优点是，vector 在头部删除或添加元素的速度很慢，在尾部添加元素的性能较好，而 deque 在头尾增删元素都具有较好的性能（大多数情况下都能在常数时间内完成）。它有两种 vector 没有的成员函数：
 
void push_front (const T & val);  //将 val 插入容器的头部
void pop_front();  //删除容器头部的元素

list容器
 
list的介绍：
 list双向链表在任何位置的插入和删除为常数时间，不支持根据下标随机存取元素，具有所有顺序容器都有的成员函数。
 list的成员函数：
 push_front 在链表最前面插入
 pop_front 删除链表最前面的元素
 sort 排序 (list 不支持 STL 的算法 sort)
 remove 删除和指定值相等的所有元素
 unique 删除所有和前一个元素相同的元素
 merge 合并两个链表, 并清空被合并的链表
 reverse 颠倒链表
 splice 在指定位置前面插入另一链表中的一个或多个元素,
 并在另一链表中删除被插入的元素
 
list的迭代器
 list容器之sort函数
 list容器的迭代器不支持完全随机访问
 不能用标准库中sort函数对它进行排序
 list自己的sort成员函数
 
list<T> classname
classname.sort(compare); //compare函数可以自己定义
classname.sort(); //无参数版本, 按<排序
 
list容器只能使用双向迭代器
 不支持大于/小于比较运算符, []运算符和随机移动
 (即类似 “list的迭代器+2” 的操作)
 
deque 容器
 
双向队列，必须包含头文件 #include ，所有适用于vector的操作， 都适用于deque，deque还有 push_front (将元素插入到容器的头部)，和 pop_front (删除头部的元素) 操作