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