双端队列 dequetype
status
date
slug
summary
tags
category
icon
password
Property
deque提供类似于vector的功能，但在序列的开头也可以有效地插入和删除元素，而vector仅支持在尾部操作。但是，与vector不同的是deque不能保证将其所有元素存储在连续的存储位置中，因此deque不允许指针偏移来访问另一个元素，否则将会导致未定义的行为发生。
双端队列是一种同时具有队列和栈的性质的一种数据结构，在队列的两头都可以进行插入和删除的操作。
- 输入受限的双端队列是指只能从队列一端输入，可以从两端输出的双端队列
- 输出受限的双端队列是指只能从队列一端输出，可以从两端输入的双端队列
- 如果双端队列允许从一端输入，从一端输出，则是普通的队列，如果双端队列只允许从一端输入和输出则是栈。因此说双端队列同时具有队列和栈两种数据结构的性质
C++ 在 STL 中也提供了一个容器
std::deque，使用前需要先引入 <deque> 头文件。定义和初始化
deque中的迭代器
迭代器的类型包括：iterator、const_iterator、reverse_iterator和const_reverse_iterator
deque.begin()：指向deque首个元素。
deque.end()：指向deque尾元素的下一个位置。
deque.rbegin()：指向deque尾元素的反向迭代器，即rbegin()指向尾元素，rbegin-1指向倒数第二个元素。
deque.rend()：指向deque头元素前一个位置的反向迭代器，即rend()指向头元素前一个位置元素，rbegin-1指向第一个元素
deque.cbegin()：指向deque首元素，与begin()相同。增加了const属性，不能用于修改元素。
deque.cend()：指向deque尾元素下一个位置，与end()相同。增加了const属性，不能用于修改元素。
deque.crbegin()：指向deque尾元素的反向迭代器，与rbegin()相同。增加了const属性，不能用于修改元素。
deque.crend()：指向deque头元素前一个位置的反向迭代器，与rend()相同。增加了const属性，不能用于修改元素。
元素的访问
方法 | 说明 |
[] 或 at() | 下标访问 |
front | 数组头元素 |
back | 数组尾元素 |
empty | 数组判空 |
size | 数组大小 |
max_size | 最大容量 |
resize | 改变大小 |
shrink_to_fit | 改变deque所占内存的大小，减少到size的大小 |
clear | 清空size大小 |
元素的修改
方法 | 说明 |
insert | 插入元素，可以是任意位置，可以插入多个元素 |
emplace | 插入元素，可以是任意位置，只能插入一个元素 |
push_back | 数组尾部插入元素，先复制元素，在将元素插入到尾部 |
emplace_back | 数组尾部插入元素，直接在数组尾部创建元素 |
push_front | 数组头部插入元素，先复制元素，在将元素插入到头部 |
emplace_front | 数组头部插入元素，直接在数组尾部创建元素 |
pop_back | 删除队尾元素 |
pop_front | 删除头部元素 |
erase | 删除元素，可以是任意位置 |
swap | 交换两个vector的内容 |
assign | 重新对vector赋值 |
get_allocator | 返回内存分配器 |