C++标准模板库(STL)中的双端队列(Deque)

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的结尾。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程