一、deque介绍

deque（双端队列）是一种索引容器，它包含在#include<deque>头文件中。它与普通的queue队列不同的是，deque可以实现在尾部插入和删除元素。

• 随机的访问双端队列中的元素，时间复杂度为O(1)
• 在首部或者尾部插入或删除元素，时间复杂度O(1)
• 插入和删除元素，是线性的，时间复杂度为O(n)

定义方法为:deque<数据类型>名字

二、deque的基本使用

对于容器而言，基本的操作都相差不大，下面列举一些deque用的比较多的函数。

• front()
• back()
• push_front()
• push_back()
• pop_front()
• pop_back()
• size()
• empty()
• shrink_to_fit()
• clear()
• insert()

代码演示：

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

int main(){
    deque<int> dq;
    //先后在首部和尾部插入元素
    dq.push_front(2);
    dq.push_back(1);
    cout << dq.size() << endl;
    //先后弹出首部和尾部的元素
    dq.pop_front();
    dq.pop_back();
    cout << dq.size() << endl;
    
    if(dq.empty()){
        cout << "容器为空" << endl;
    }
    for (int i = 0; i < 10; i++){
        //分别进行头插和尾插
        dq.push_front(i);
        dq.push_back(i);
    }
    cout << "容器首部的元素和尾部的元素分别是:"<< dq.front() << " " << dq.back() << endl;

    for(auto x :dq){//遍历容器，并输出容器中的元素
        cout << x << " ";
    }

    
    dq.clear();//清空容器
    //在容器中使用insert,第一个参数需要是迭代器类型
    dq.insert(dq.begin(), 5);//在容器的首部插入元素5
    
    cout << endl <<dq.front() << endl;
    cout << dq.size();
    return 0;
}

运行结果：

三、基本应用

现在我们要实现一个队列，既能实现在首部和尾部的插入删除，还要实现能够在队列中间插入删除，并且要求时间复杂度是线性的。

那么我们可以使用两个双端队列来实现，一个left,一个right。在合适条件的时候我们让left的尾部等于right的头部或者right的头部等于left的尾部。

这样当我们需要往中间插入或删除的时候就只需要判断left的大小和right的大小既可。

代码演示:

//为了避免定义不明确所以首字母大写
deque<int> Left,Right;

//头部插入
void pushFront(int val){
    Left.push_front(val);
    /*
    当插入元素后如果出现这种情况时
    Left:3,5,6,1,4
    Right:5,1,0
    我们就需要将Left的尾部添加到Right的头部，然后弹出Left的尾部
    这样的操作完之后
    Left:3,5,6,1
    Right:4,5,1,0
    这样的话当我们需要在中间插入或删除时就非常方便
    */ 
    if(Left.size() == Right.size() + 2){
        Right.push_front(Left.back());
        Left.pop_back();
    }
}

//尾部插入
void pushBack(int val){
    Right.push_back(val);
    //原理同上，简单模拟一下既可,主要是让left的大小与right的大小相同,或者left的大小比Right大1
    //因为队列中元素的个数可能是奇数也可能是偶数
    /*
    l:3,5,4,6
    r:5,9,7,3,0
    操作后
    l:3,5,4,6,5
    r:9,7,3,0
    */
    if(Left.size() + 1 == Right.size()){
        Left.push_back(Right.front());
        Right.pop_front();
    }
}

//中间插入
void pushMiddle(int val){
    if(Left.size() + 1 == Right.size()){
        Right.push_front(Left.back());
        Left.pop_back();
    }
    Left.push_back(val);
}

//头部删除
int popFront(){
    if(Left.empty()){//队列为空，无法弹出元素返回-1
        return -1;
    }
    int val = Left.front();
    if(Left.size() + 1 == Right.size()){
        Left.push_back(Right.front());
        Right.pop_front();
    }
    cout << "弹出元素为:" << val << endl;
    return val;
}

//尾部删除
int popBack(){
   if(Left.empty()){
       return -1;
   }
   int val = 0;
   if(Right.empty()){
       val = Left.back();
       Left.pop_back();
   }
   else{
       val = Right.back();
       Right.pop_back();
       if(Left.size() == Right.size() + 2){
           Right.push_front(Left.back());
           Left.pop_back();
       }
   }
   cout << "弹出元素为:" << val << endl;
   return val;
}

//中间删除
int popMiddle(){
    if(Left.empty()){
        return -1;
    }
    int val = Left.back();
    Left.pop_back();
    if(Left.size() + 1 == Right.size()){
        Left.push_back(Right.front());
        Right.pop_front();
    }
    return val;
}

主要的思想是始终要让left的大小等于right的大小，或者让left的大小比right大1。