双向队列deque

双向队列也是队列，是最为常见的一种数据结构，双向队列在STL中有deque的实现。包含双向队列在内，队列中的元素满足FIFO（先进先出）。主要特点如下：

元素需满足FIFO：First In First Out
出口端称为队头（Front），入口端称为队尾（Rear）
可以使用数组或者链表来存储数据
操作主要有入队（Enqueue）和出队（Dequeue）
可以根据需要实现循环队列或者双向队列
只能在队尾插入数据，在队头删除数据
关于队列的说明内容可参看：https://blog.csdn.net/liumiaocn/article/details/108091698

头文件和命名空间

#include
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