deque容器
双端队列是 Double Ended Queue 的首字母缩写。 它是一个序列容器，可以改变它的运行时大小。 容器是保存相同类型数据的对象。 序列容器严格按线性顺序存储元素。
deque 的元素可以分散在不同的内存块中。 容器存储必要的信息以允许在恒定时间内直接访问任何元素。与向量不同，deque 不能保证将所有元素存储在连续的内存位置。 因此，它不允许通过偏移指针直接访问数据。 但它允许使用下标运算符 [ ] 直接访问任何元素。
双端队列可以在运行时根据需要从两端收缩或扩展。 内部分配器自动满足存储要求。 双端队列提供与向量类似的功能，但提供了从任意端插入和删除数据的有效方法。
零大小的双端队列也是有效的。 在这种情况下， deque.begin() 和 deque.end() 指向相同的位置。 但是调用 front() 或 back() 的行为是未定义的。
image.png
deque容器常用api
1.deque构造函数
deque<T> queT;//queue采用模板类实现，queue对象的默认构造形式
deque<T> queT(size);//构造大小为size的deque，其中值为T类型的默认值
deque<T> queT(size, val);//构造大小为size的deque，其中值为val
deque(const deque &que);//拷贝构造函数
deque(input_iterator start, input_iterator end);//迭代器构造函数
2.deque存取、插入和删除操作
back();//返回最后一个元素
front();//返回第一个元素
insert();//
pop_back();//删除尾部的元素
pop_front();//删除头部的元素
push_back();//在尾部加入一个元素
push_front();//在头部加入一个元素
at();//访问指定位置元素
注：queue只有push和pop方法，在尾部加入和删除元素。
3.deque赋值操作
operator[] (size_type n);//重载[]操作符
4.deque大小操作
empty();//判断队列是否为空
size();//返回队列的大小
deque构造
void printDeque(deque<int> d) {
// const_iterator只读迭代器
for (deque<int>::const_iterator it = d.begin(); it != d.end(); it++)
{
cout << " "<< *it;
}
cout << endl;
}
deque<int> d;
d.push_back(11);
d.push_back(12);
d.push_back(13);
d.push_back(14);
printDeque(d);
deque<int> d2(d.begin(), d.end());
d2.push_back(44444);
//交换
d.swap(d2);
printDeque(d);
deque插入数据
deque<int> d;
d.push_back(11); // 尾插
d.push_back(12);
d.push_back(13);
d.push_back(14);
d.push_front(666); // 头插
d.push_front(777);
printDeque(d); // 777 666 11 12 13 14
d.pop_back(); //尾删
d.pop_front(); // 头删
printDeque(d); // 666 11 12 13
deque<int>d2;
d2.push_back(77);
d2.push_back(88);
d2.insert(d2.begin(), d.begin(), d.end());
printDeque(d2); // 666 11 12 13 77 88
deque排序
#include<algorithm>
bool myCompare(int v1, int v2) {
return v1 > v2;
}
void test01() {
deque<int> d;
d.push_back(11); // 尾插
d.push_back(12);
d.push_back(13);
d.push_back(14);
d.push_front(666); // 头插
d.push_front(777);
printDeque(d); // 777 666 11 12 13 14
// sort(d.begin(), d.end()); 使用默认的排序规则
sort(d.begin(), d.end(), myCompare);
printDeque(d);
}
queue容器
queue容器常用函数
ront()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
pop()：删除 queue 中的第一个元素。
size()：返回 queue 中元素的个数。
empty()：如果 queue 中没有元素的话，返回 true。
emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
swap(queue<T> &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。
#include <iostream>
#include<string>
#include <queue>
#include <deque>
#include <list>
using namespace std;
int main() {
queue<string, list<string>> q1; // 物理结果为链表
// queue<string, deque<string>> q2; 物理结构为数组
// queue<string> q3; 物理结构为数组
q1.push("李思");
q1.push("王五");
q1.emplace("alex"); //效率更高
q1.push("赵六");
q1.push("力气");
while (!q1.empty())
{
cout <<" q1.front = "<<q1.front()<<endl;
q1.pop();
}
return 0;
}
网友评论