C++标准模板库（STL）deque双端队列
一. 定义与基本概念
在C++的标准模板库（STL）中，deque（双端队列，发音为“deck”）是一种序列容器，位于<deque>头文件中。类似vector，支持随机访问元素，但在两端进行插入和删除操作更为高效。deque中的元素在内存中可能不是连续存储的，而是由多个固定大小的块组成，每个块内部是连续存储的。
二. 创建deque对象
默认构造：可以创建一个空的deque对象。
std::deque<int> myDeque;
创建了一个空的、用于存储int类型元素的deque。
指定大小构造：可以创建具有特定大小的deque，并可选择初始化元素的值。
std::deque<int> myDeque(5);
创建了一个包含5个int类型元素的deque，这些元素会被默认初始化（对于基本类型int，默认值为0）；
std::deque<int> myDeque(5, 10);
则创建了一个包含5个元素且每个元素都初始化为10的deque。
从其他容器初始化：可以使用另一个容器（如数组）来初始化deque。
int arr[] = {1, 2, 3};
std::deque<int> myDeque(arr, arr + sizeof(arr)/sizeof(arr[0]));这里使用数组arr的元素来初始化deque myDeque。
三. deque的基本操作
1. 元素访问
使用[]运算符：与vector类似，可以通过[]运算符来访问deque中的元素。
std::deque<int> myDeque = {1, 2, 3};
std::cout << myDeque[1] << std::endl;这里通过[]运算符访问myDeque中的第二个元素，输出为2。
使用at()方法：at()方法也用于访问元素，并且会进行边界检查。
std::deque<int> myDeque = {1, 2, 3};
std::cout << myDeque.at(2) << std::endl;访问myDeque中的第三个元素，如使用at()方法访问超出范围的索引，会抛出std::out_of_range异常。
2. 添加元素
push_back()和push_front()：push_back()用于在deque的末尾添加一个元素，push_front()用于在deque的开头添加一个元素。
std::deque<int> myDeque; myDeque.push_back(3); myDeque.push_front(1);
此时myDeque包含两个元素，1在开头，3在末尾。
insert()（在指定位置插入元素）：可以在deque的指定位置插入一个或多个元素。
std::deque<int> myDeque = {1, 3};
std::deque<int>::iterator it = myDeque.begin();
++it;
myDeque.insert(it, 2);这里在deque中1和3之间插入了元素2。
3. 删除元素
pop_back()和pop_front()：pop_back()用于删除deque末尾的一个元素，pop_front()用于删除deque开头的一个元素。
std::deque<int> myDeque = {1, 2, 3};
myDeque.pop_front();
myDeque.pop_back();操作后myDeque中只剩下元素2。
erase()（删除指定位置的元素）：可以删除deque中指定位置的元素。
std::deque<int> myDeque = {1, 2, 3};
std::deque<int>::iterator it = myDeque.begin();
++it;
myDeque.erase(it);这里删除了myDeque中的元素2。
4. 获取deque的大小和容量
size()：返回deque中当前元素的个数。例如，std::deque<int> myDeque = {1, 2, 3}; std::cout << myDeque.size() << std::endl;会输出3，表示deque中有3个元素。
capacity()（在某些实现中）：一些deque的实现可能提供capacity()方法来表示deque在不重新分配内存的情况下能够容纳的最大元素数量，但这不是标准要求的操作。与vector不同，deque的内存管理机制使得它不需要像vector那样频繁地重新分配内存来扩展容量。
四. 迭代器操作
deque提供了随机访问迭代器，支持与vector类似的迭代器操作。
std::deque<int> myDeque = {1, 2, 3};
// 正向遍历
for (std::deque<int>::iterator it = myDeque.begin(); it!= myDeque.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 反向遍历
for (std::deque<int>::reverse_iterator rit = myDeque.rbegin(); rit!= myDeque.rend(); ++rit) {
std::cout << *rit << " ";
}
std::cout << std::endl;这里使用begin()、end()、rbegin()和rend()方法分别获取正向和反向迭代器的起始和结束位置。
五. deque的特性与注意事项
内存管理与性能：deque的内存布局使得它在两端插入和删除元素的效率很高（时间复杂度为$O(1)$），类似于list在两端操作的效率。同时，它支持随机访问，随机访问元素的时间复杂度为$O(1)$，这一点与vector相同。然而，由于其内存结构相对复杂，与vector相比，在某些操作（如中间元素的插入和删除）上可能会有一些性能差异。
与vector和list的比较
与vector相比，deque在两端操作更高效，而vector在末尾添加元素的操作也很高效，但在开头添加元素效率较低。并且vector在内存重新分配时可能会导致性能下降，而deque的内存管理相对更灵活。
与list相比，deque支持随机访问，而list不支持。list在中间插入和删除元素的效率很高，但随机访问效率很低。
迭代器失效：在对deque进行插入或删除操作时，可能会导致迭代器失效。与vector类似，在deque中插入或删除元素可能会使指向该元素之后的迭代器失效，需要注意在操作后重新获取有效的迭代器。
