C++ Deque

在 C++ 中，deque（双端队列） 是一种可以在队列的头部和尾部添加和移除元素的队列。它支持 FIFO（先进先出）和 LIFO（后进先出）操作，比队列更具灵活性。在 C++ 中，STL deque 是一个顺序容器，可以高效地在头部和尾部插入和删除元素。

与只允许在尾部插入、在头部移除的标准 队列 不同，deque 通过允许在两端进行操作提供了更大的灵活性。它还允许使用索引位置访问元素，这使其适用于需要随机访问和动态调整大小的场景。如果我们想使用 deque 容器，我们必须包含 <deque> 头文件。

语法

它具有以下语法：

在这个语法中，

• object_type： object_type 参数决定了 deque 将存储的组件类型，例如 int、string 和自定义类。
• deque_name： 它代表分配给 deque 的标识符和变量的名称。
• ;： 根据 C++ 语法说明，它结束语句。

简单的 C++ Deque 示例

让我们以一个例子来说明 C++ 中的 deque。

输出

7 8 5 1 2 9

说明

在这个例子中，我们创建了一个包含六个元素的整数 deque：{7, 8, 5, 1, 2, 9}。使用基于范围的 for 循环，它会遍历 deque 并打印每个元素，元素之间用空格分隔。之后，deque 允许在两端进行快速的插入和删除，这在某些场景下比 数组 或 向量 更具灵活性。

Deque 的基本操作

在 C++ 的 deque 中执行了几个操作。其中一些如下：

1) 在 Deque 中创建和插入元素

要声明一个 deque，请使用 deque 关键字，后跟用尖括号 (< >) 括起来的数据类型，以及变量名。标准模板库 (STL) 提供了 deque 作为一种容器，它允许在两端进行快速的插入和删除。

在 C++ deque 中，我们可以使用 push_back() 和 push_front() 函数在任一端执行插入和删除操作。如果我们想在特定位置插入元素，可以使用 insert() 方法。

在 Deque 中创建和插入元素的示例

让我们以一个例子来说明如何在 C++ 中创建和插入元素到 deque 中。

输出

Deque elements are: 1 5 7 15 18 27

说明

在这个例子中，我们使用了 push_front() 函数在开头插入值，并使用 push_back() 函数在末尾插入值。之后，emplace_front() 和 emplace_back() 函数的作用与 push_front() 和 push_back() 函数相同，但它们更有效地直接插入临时或构造的值。

2) 访问 Deque 中的元素

deque 的元素可以直接使用索引表示法（包含方括号 []）进行访问。Deque 是 0 索引的，这意味着第一个元素位于索引 0，第二个元素位于索引 1，依此类推。它允许从容器内的特定位置快速轻松地检索元素。它还提供了 front() 和 back() 方法，可以轻松访问列表的第一个和最后一个元素。

访问 Deque 中元素的示例

现在，让我们看一个 C++ 示例，演示如何访问 deque 中的元素。

输出

App at index 0 is: Snapchat
App at index 1 is: Twitter
The first app (front) is: Snapchat
The last app (back) is: Instagram
App at index 2 (using at()) is: Whatsapp
App at index 3 (using at()) is: Instagram

说明

在这个例子中，我们创建了一个名为 socialmedia_apps 的 deque，其中包含社交媒体应用程序名称列表，并演示了如何使用索引表示法、front()、back() 和 at() 方法来获取其内容。之后，它会在控制台中显示每个可访问的元素。

3) 修改 Deque 元素

要更改 deque 中特定元素的值，请使用用方括号 [] 括起来的索引和 at() 方法。这些函数提供对元素位置的直接访问和值替换。虽然 [] 运算符允许更快的访问，但 at() 函数更安全，因为它会执行边界检查，如果索引超出范围则会抛出异常。

修改 Deque 元素的示例

现在，让我们看一个 C++ 示例，演示如何修改 deque 元素。

输出

Updated list of the Fruitnames:
Pomegranate
Custard Apple
Watermelon
Musk melon

说明

在这个例子中，我们使用索引访问运算符 [] 和 at() 函数初始化了一个包含水果名称的 deque。之后，我们在 deque 的开头插入“Banana”，在末尾插入“Grapes”。

4) 从 Deque 中移除元素

在 C++ 中，deque 容器允许从队列的头部和尾部进行高效的移除操作。pop_front() 函数用于移除队列头部的元素，而 pop_back() 函数用于移除队列尾部的元素。这些函数会永久删除相应的元素，而不会返回它们。

从 Deque 中移除元素的示例

现在，让我们看一个 C++ 示例，演示如何从 deque 中移除元素。

输出

The Service Queue elements are:
Volvo
BMW
Ford
Mazda
The updated Service Queue elements are:
BMW
Ford

说明

在这个例子中，我们演示了如何使用 deque 来处理汽车品牌服务队列。之后，它会显示队列中的所有元素，然后使用 pop_front() 和 pop_back() 移除第一个和最后一个条目。

5) Deque 大小

在 C++ 中，size() 方法返回 deque 容器当前包含的元素数量。它是一个常数时间操作，有助于监视队列大小，这对于实际应用程序中的逻辑控制、迭代和状态报告很有用。

Deque 大小示例

现在，让我们看一个 C++ 示例，演示 deque 的大小。

输出

Number of patients waiting: 4

说明

这是一个诊所病人队列的例子。.size() 函数表示当前有多少病人在等待。

6) 检查 Deque 是否为空

在 C++ 中，empty() 方法确定 deque 容器是否包含任何元素。如果 deque 为空，则返回 true (1)，如果包含至少一个元素，则返回 false (0)。在实时场景中非常有用，例如当只有在容器包含数据时才应执行操作，如任务处理、用户输入响应和队列管理。

检查 Deque 是否为空的 C++ 示例

现在，让我们看一个 C++ 示例，演示如何检查 deque 是否为空。

输出

No books have been returned yet.

说明

在这个例子中，我们创建了一个名为 returnbox 的空 deque，并使用 empty() 函数检查它是否包含任何元素。它会根据 return box 是否包含书籍打印不同的消息。

7) 遍历 Deque

使用循环来检索和处理 deque 中的每个元素。基于索引的循环允许按位置访问，当元素位置很重要时适用。基于范围的 for-each 循环（在 C++11 中添加）更易读，当只关注元素本身时很有用。

遍历 Deque 的示例

现在，让我们看一个 C++ 示例，演示如何遍历 deque。

输出

Medication Schedule - (using an index-based loop):
Aspirin
Vitamin D
Antibiotic
Cough Syrup
Medication Schedule - (using a for-each loop):
Aspirin
Vitamin D
Antibiotic
Cough Syrup

说明

在这个例子中，我们创建了一个包含药品列表的 deque。它首先使用基于索引的 for 循环（按位置访问元素）打印药物计划。之后，它使用更简洁的 for-each 循环（直接遍历元素）输出相同的列表。

C++ Deque 函数

下表显示了 Deque 的几个函数，它们在 C++ 中执行操作。

Deque 的其他常用操作

C++ 中 Deque 的其他一些常用操作如下：

C++ Deque 迭代器

在 C++ 中，deque 容器支持随机访问迭代器。这些迭代器可以指向 deque 中的元素，并提供与 vector 中找到的元素相同的遍历、修改和访问功能。

语法

声明 Deque 迭代器的语法

C++ Deque 迭代器示例

现在，让我们看一个 C++ 示例，演示 deque 迭代器。

输出

Temperature log for the day:
36.5°C
37°C
36.8°C
37.2°C
36.9°C

说明

在这个例子中，我们初始化了一个包含每日温度信息的双精度值 deque。定义了一个迭代器 q 并使用它来遍历 deque，通过 for 循环访问每个元素。在遍历过程中，每个温度值都打印有“°C”符号，表示摄氏度。

使用 Deque 迭代器访问元素

Deque 迭代器通过指向内存位置来提供对元素的访问。可以使用算术运算（如 begin() + i）移动迭代器到任何位置，并使用 * 解引用来检索值。

使用 Deque 迭代器访问元素的示例

现在，让我们看一个 C++ 示例，演示如何使用 deque 迭代器访问元素。

输出

First ID: 11
Second ID: 12
Last ID: 13

说明

在这个例子中，我们创建了一个包含 ID 的整数 deque，并使用迭代器 q 访问特定元素。通过使用 begin() 和 end() 将迭代器分配到相应的位置，它会生成第一个、第二个和最后一个 ID。

时间复杂度

下表显示了在 deque 上执行的几个操作的时间复杂度。

C++ Deque 选择题

1) 在 C++ 中使用 deque 需要哪个头文件？

1. <vector>
2. <deque>
3. <array>
4. <list>

2) 在 deque 的开头插入元素的time complexity是多少？

1. O(1)
2. O(n)
3. O(log n)
4. O(n log n)

3) 哪个函数用于移除 deque 的最后一个元素？

1. remove_back()
2. delete_back()
3. pop_back()
4. erase_back()

4) deque<int>::iterator 代表什么？

1. 一个对象
2. 指针
3. 算法
4. 整数 deque 的迭代器

5) 关于 deque，以下哪个说法是正确的？

1. 它只支持在末尾进行 push 和 pop 操作
2. 它仅使用数组实现
3. 它支持随机访问迭代器
4. 它的插入速度比 list 慢