上查看所有课程
在 C++ 中，STL deque 是一个顺序容器，它提供了双端队列数据结构的功能。
在普通队列中，元素从尾部添加，从头部移除。但是，在 deque 中，我们可以从**头部**和**尾部**插入和移除元素。
要了解有关 deque 的更多信息，请访问 Deque 数据结构。
创建 C++ STL Deque
为了在 C++ 中创建 deque，我们首先需要包含 deque 头文件。
#include <deque>导入此文件后，我们可以使用以下语法创建 deque
deque<type> dq;在此，type 表示我们要在 deque 中存储的数据类型。例如，
// create a deque of integer data type
deque<int> dq_integer;
// create a deque of string data type
deque<string> dq_string;初始化 Deque
我们可以通过以下方式初始化 C++ deque
// method 1: initializer list
deque<int> deque1 = {1, 2, 3, 4, 5};
// method 2: uniform initialization
deque<int> deque2 {1, 2, 3, 4, 5};在此，deque1 和 deque2 都用值**1**、**2**、**3**、**4**、**5** 初始化。
示例：C++ Deque
#include <iostream>
#include <deque>
using namespace std;
// function prototype
void display_deque(deque<int>);
int main() {
// uniform initialization
deque<int> deque1 {1, 2, 3, 4, 5};
cout << "deque1 = ";
// display elements of deque1
for (int num : deque1) {
cout << num << ", ";
}
return 0;
}输出
deque1 = 1, 2, 3, 4, 5,
在上面的示例中，我们使用统一初始化声明并初始化了一个名为 deque1 的 deque。
deque<int> deque1 {1, 2, 3, 4, 5};然后，我们使用 范围 for 循环显示了 deque 的内容。
for (int num : deque1) {
cout << num << ", ";
}创建 C++ Deque 的其他方法
使用**填充构造函数方法**，我们可以通过指定大小和元素来初始化 deque。例如，
// fill constructor
deque<int> deque1(5, 12);在这里，我们初始化了一个大小为 **5**，值为 **12** 的 deque。
这相当于
deque<int> deque1 = {12, 12, 12, 12, 12};请注意，所有元素都具有相同的值。
我们还可以通过从另一个 deque 复制元素来初始化 deque。这被称为**范围方法**。
我们可以使用**范围方法初始化**将一个 deque 复制到另一个。
deque<int> deque1 = {1, 2, 3, 4, 5};
// copy all elemnts of deque1 to deque2
deque<int> deque2(deque1.begin(), deque1.end());在这里，我们首先创建了一个名为 deque1 的 deque。然后，我们通过复制 deque1 的所有元素创建了另一个名为 deque2 的 deque。
我们还可以指定要复制的元素范围。例如，
// copy elements from index 1 to index 2 of deque1
deque<int> deque3(deque1.begin() + 1, deque1.begin() + 3);在这里，起点是 deque1.begin() + 1，它指向 deque1 的**索引 1**。终点是 deque1.begin() + 3，它指向**索引 3**。
但是，deque3 将是 {2, 3}，因为终点是排他的，即终点不会被复制。
C++ Deque 方法
在 C++ 中，deque 类提供了各种方法来对 deque 执行不同的操作。
| 方法 | 描述 |
|---|---|
push_back() |
在尾部插入元素 |
push_front() |
在头部插入元素 |
pop_back() |
从尾部移除元素 |
pop_front() |
从头部移除元素 |
front() |
返回头部元素 |
back() |
返回尾部元素 |
at() |
设置/返回指定索引处的元素 |
size() |
返回元素数量 |
empty() |
如果 deque 为空，则返回 true |
向 Deque 插入元素
我们可以使用以下方法插入元素
push_back()- 在末尾插入元素push_front()- 在开头插入元素
例如，
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {2, 3};
cout << "Initial Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
// add integer 4 at the back
nums.push_back(4);
// add integer 1 at the front
nums.push_front(1);
cout << "\nFinal Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}输出
Initial Deque: 2, 3, Final Deque: 1, 2, 3, 4,
在上面的示例中，我们初始化了一个名为 nums 的整数 deque，其元素为 **2** 和 **3**。
然后，我们将整数 **4** 插入到 nums 的尾部。
// nums = {2, 3, 4}
nums.push_back(4);最后，我们将 **1** 插入到 deque 的头部。
// nums = {1, 2, 3, 4}
nums.push_front(1);注意：我们也可以使用 insert() 和 emplace() 方法向 deque 添加元素。
从 Deque 访问元素
我们可以使用以下方法访问 deque 的元素
front()- 返回头部元素back()- 返回尾部元素at()- 返回指定索引处的元素
例如，
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {1, 2, 3};
cout << "Front element: " << nums.front() << endl;
cout << "Back element: " << nums.back() << endl;
cout << "Element at index 1: " << nums.at(1) << endl;
cout << "Element at index 0: " << nums[0];
return 0;
}输出
Front element: 1 Back element: 3 Element at index 1: 2 Element at index 0: 1
在上面的例子中：
nums.front()- 返回 deque 头部元素，即 **1**nums.back()- 返回 deque 尾部元素，即 **3**nums.at(1)- 返回**索引 1** 处的元素，即 **2**nums[0]- 返回**索引 0** 处的元素，即 **1**
注意：虽然我们可以使用 [] 运算符访问 deque 元素，但更推荐使用 at() 方法。
这是因为 at() 在 deque 越界时会抛出异常，而 [] 会给出垃圾值。
更改 Deque 的元素
我们可以使用 at() 方法更改 deque 的元素。例如，
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums = {1, 2};
cout << "Initial Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
// change elements at the index
nums.at(0) = 3;
nums.at(1) = 4;
cout << "\nUpdated Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}输出
Initial Deque: 1, 2, Updated Deque: 3, 4,
在上面的示例中，nums deque 的初始内容是 {1, 2}。
然后，我们使用 at() 方法更改指定索引处的元素
nums.at(0) = 2;- 将**索引 0** 的值更改为 **3**nums.at(1) = 4;- 将**索引 1** 的值更改为 **4**
从 Deque 中移除元素
我们可以使用以下方法移除 deque 的元素
pop_back()- 从尾部移除元素pop_front()- 从头部移除元素
例如，
#include <iostream>
#include <deque>
using namespace std;
// function prototype for display_deque()
void display_deque(deque<int>);
int main() {
deque<int> nums {1, 2, 3};
cout << "Initial Deque: ";
display_deque(nums);
// remove element from the back
nums.pop_back();
cout << "\nDeque after pop_back(): ";
display_deque(nums);
// remove element from the front
nums.pop_front();
cout << "\nDeque after pop_front(): ";
display_deque(nums);
return 0;
}
// utility function to print deque elements
void display_deque(deque<int> dq){
for (const int& num : dq) {
cout << num << ", ";
}
}输出
Initial Deque: 1, 2, 3, Deque after pop_back(): 1, 2, Deque after pop_front(): 2,
在上面的示例中，我们初始化了一个名为 nums 的整数 deque，其元素为 {1, 2, 3}。
然后，我们使用 pop_back() 和 pop_front() 从 nums 中移除元素。
nums.pop_back(); // removes 3
names.pop_front(); // removes 1所以最终的 deque 变为 {2}。
C++ Deque 迭代器
迭代器可以用来指向 deque 元素的内存地址。
我们可以使用以下语法创建 deque 迭代器
deque<type>::iterator itertaor_name;例如，
// iterator for int deque
deque<int>::iterator iter_int;
// iterator for double deque
deque<double>::iterator iter_double;使用 Deque 迭代器访问元素
我们可以使用迭代器访问 deque 中的元素。例如，
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {1, 2, 3};
// declare an iterator to deque
deque<int>::iterator dq_iter;
// make iterator point to first element
dq_iter = nums.begin();
// print value pointed by itertor using *
int first_element = *dq_iter;
cout << "nums[0] = " << first_element << endl;
// make iterator point to element at index 1
dq_iter = nums.begin() + 1;
int element_index1 = *dq_iter;
cout << "nums[1] = " << element_index1 << endl;
// make iterator point to last element
dq_iter = nums.end() - 1;
int last_element = *dq_iter;
cout << "nums[2] = " << last_element;
return 0;
}输出
nums[0] = 1 nums[1] = 2 nums[2] = 3
在上面的示例中，我们使用了迭代器来访问 deque 中的元素。最初，我们创建了一个可以指向整数 deque 的迭代器
deque<int>::iterator dq_iter;然后，我们使用了 dq_iter 迭代器指向以下元素
1. 第一个元素
dq_iter = nums.begin();在这里，begin() 方法返回一个指向第一个元素的迭代器。
2. 索引为 1 的元素
dq_iter = nums.begin() + 1;代码 begin() + 1 返回一个指向**索引 1** 处的元素的迭代器。
注意：泛化来说，nums.begin() + i 指向索引 i 处的元素。
3. 最后一个元素
dq_iter = nums.end() - 1;请注意，我们使用的是 nums.end() - 1 而不是 nums.end()。
这是因为 end() 方法的迭代器指向最后一个元素之后的迭代器。所以，为了获得最后一个元素，我们减去了 **1**。
4. 获取元素值
使用 dq_iter 指向某个元素后，我们使用**解引用运算符** * 来获取该元素的值
// point to the first element
dq_iter = nums.begin();
// returns 1
int first_element = *dq_iter;在这里，*dq_iter 给出 dq_iter 迭代器所指向元素的值。
常见问题
我们可以使用 erase() 方法移除指定索引处的元素。例如，
deque<int> nums {1, 2, 3, 4, 5};
// removes element at index 1
// nums becomes {1, 3, 4, 5}
nums.erase(nums.begin() + 1);上面的代码从 nums deque 中移除了**索引 1** 处的元素。
所以，我们可以使用以下方式删除任何 index 处的元素
nums.erase(nums.begin() + index);我们也可以在这里使用 erase() 方法。
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {1, 2, 3, 4, 5};
// removes elements from index 1 to 2
nums.erase(nums.begin() + 1, nums.begin() + 3);
for(auto num: nums) {
cout << num << ", ";
}
return 0;
}输出
1, 4, 5,
最初，nums 包含元素 {1, 2, 3, 4, 5}。
然后我们使用以下方式移除从**索引 1** 到**索引 2** 的元素，
nums.erase(nums.begin() + 1, nums.begin() + 3); 请注意，范围的终点是 nums.begin() + 3，但**索引 3** 的元素没有被移除。
这是因为 erase() 函数的终点是排他的。
我们可以使用 clear() 方法来擦除 deque 的所有元素。
deque<int> nums {1, 2, 3};
// clear all the elements
nums.clear();我们可以使用 size() 方法来查找 deque 中的元素数量。
deque<int> nums {1, 2};
// returns 2
cout << nums.size();我们也可以使用 empty() 方法来确定 deque 是否为空
// returns false
cout << nums.empty();是的，我们可以使用 auto 关键字来初始化 deque 迭代器。但是，我们不能仅使用 auto 来声明一个迭代器而不初始化它。
例如，假设我们有一个名为 nums 的 int deque。那么以下代码
auto dq_iter = nums.begin();等同于
deque<int>::iterator dq_iter = nums.begin();但是，以下代码是无效的
auto dq_iter; // invalid这是因为我们没有初始化 dq_iter。因此，C++ 无法推断其类型，从而产生错误。