C++标准模板库（STL）中的双端队列（Deque）

双端队列是一种具有两端扩展和收缩的序列容器。它们类似于向量，但在插入和删除元素时更有效。与向量不同，可能无法保证连续的存储分配。

双端队列基本上是一种数据结构——双端队列的实现。队列数据结构只允许在末尾插入和在前端删除。这就像生活中的队列，人们从前面移开，从后面添加。双端队列是队列的特殊情况，其中在两端都可以进行插入和删除操作。

deque的函数与vector相同，但添加了push和pop操作，用于前端和后端。

进行deque各种操作的时间复杂度如下：

访问元素-O（1）
插入或删除元素-O（N）
在开头或结尾插入或删除元素-O（1）

// CPP程序实现STL中的双端队列
#include 
#include 
 
using namespace std;
 
void showdq(deque g)
{
    deque::iterator it;
    for (it = g.begin(); it != g.end(); ++it)
        cout << '\t' << *it;
    cout << '\n';
}
 
int main()
{
    deque gquiz;
    gquiz.push_back(10);
    gquiz.push_front(20);
    gquiz.push_back(30);
    gquiz.push_front(15);
    cout << "双端队列gquiz为：";
    showdq(gquiz);
 
    cout << "\ngquiz.size()：" << gquiz.size();
    cout << "\ngquiz.max_size()：" << gquiz.max_size();
 
    cout << "\ngquiz.at(2)：" << gquiz.at(2);
    cout << "\ngquiz.front()：" << gquiz.front();
    cout << "\ngquiz.back()：" << gquiz.back();
 
    cout << "\ngquiz.pop_front()：";
    gquiz.pop_front();
    showdq(gquiz);
 
    cout << "\ngquiz.pop_back()：";
    gquiz.pop_back();
    showdq(gquiz);
 
    return 0;
}

输出结果

双端队列gquiz为：    15    20    10    30

gquiz.size()：4
gquiz.max_size()：4611686018427387903
gquiz.at(2)：10
gquiz.front()：15
gquiz.back()：30
gquiz.pop_front()：    20    10    30

gquiz.pop_back()：    20    10

时间复杂度： O（1）

空间复杂度： O（1）

Deque的方法

方法	定义
deque::insert()	插入一个元素。返回一个指向新插入元素中第一个的迭代器。
deque::rbegin()	返回一个反向迭代器，指向deque的最后一个元素（即其反向开头）。
deque::rend()	返回一个反向迭代器，指向deque开始的位置之前（也就是其反向结尾）。
deque::cbegin()	返回一个指向容器第一个元素的常迭代器，即该迭代器不能用于修改，只能遍历deque。
deque::max_size()	返回一个deque容器能够容纳的最大元素数量。
deque::assign()	将值分配给相同或不同的deque容器。
deque::resize()	改变deque的大小的函数。
deque::push_front()	从deque的前面插入元素的函数。
deque::push_back()	从deque的后面插入元素的函数。
deque::pop_front() 和 deque::pop_back()	pop_front()函数用于从deque前面弹出或删除元素。 pop_back()函数用于从deque后面弹出或删除元素。
deque::front() 和 deque::back()	front()函数用于引用deque容器的第一个元素。 back()函数用于引用deque容器的最后一个元素。
deque::clear() 和 deque::erase()	clear()函数用于删除deque容器的所有元素，从而使其大小为0。 erase()函数用于从指定的位置或范围删除容器中的元素。
deque::empty() 和 deque::size()	empty()函数用于检查deque容器是否为空。 size()函数用于返回deque容器的大小或元素数量。
deque::operator= 和 deque::operator[]	operator=运算符用于通过替换现有内容分配新内容到容器中。 operator[]运算符用于引用操作符内给出位置处的元素。
deque::at() 和 deque::swap()	at()函数用于引用作为参数给出的位置处的元素。 swap()函数用于将一个deque的内容与附有相同类型和大小的另一个deque进行交换。
deque::begin() 和 deque::end	begin()函数用于返回指向deque容器的第一个元素的迭代器。 end()函数用于返回指向deque容器的最后一个元素的迭代器。
deque::emplace_front() 和 deque::emplace_back()	emplace_front()函数用于向deque容器中插入一个新元素。新元素添加到deque的开头。 emplace_back()函数用于向deque容器中插入一个新元素。新元素添加到deque的结尾。