C++ 中 Queue 和 Deque 的区别

在本文中，我们将讨论 C++ 中队列 (Queue) 和双端队列 (Deque) 的区别。但在讨论它们的区别之前，我们必须先了解队列和双端队列。

队列简介

队列是 C++ 中一种基本的 C++ 数据结构，它遵循“先进先出”(FIFO) 的概念。元素按照“先到先服务”的规则添加到队尾并从队头取出。由于其系统的排列方式，队列在作业调度、广度优先搜索引擎以及计算机网络中的请求管理等场景中非常有用，在这些场景中，任务或信息必须按照其接收的顺序进行处理。

在 C++ 中有几种实现队列的方法，但最流行的两种是使用标准库或创建自定义实现。C++ 提供了一个名为 std::queue 的灵活的标准模板库 (STL) 容器，通过封装其功能来简化队列的实现。开发人员可以通过包含头文件来利用这个现成的解决方案，节省开发过程中的时间和精力。

队列在后台主要由两个操作组成：入队 (Enque) 和 出队 (Deque)。出队从队列的头部取出一个元素，而入队则将一个元素添加到队列的尾部。通过保持元素的顺序，这些操作确保了队列中最旧的元素将始终是第一个被出队的元素。除了入队和出队之外，更常见的操作还包括查看 (在不弹出元素的情况下查看队头元素) 和检查队列是否为空。

在创建自定义 C++ 队列时，开发人员经常使用数组或链表等数据结构来存储元素。数组提供对元素的恒定时间访问；但是，如果超出容量，可能需要重新调整大小。另一方面，链表具有少量的开销，但提供了动态内存分配，从而使得插入和删除操作高效。这两种数据结构的选择受到几个因素的影响，包括入队和出队操作的频率以及相应队列的预期大小。

C++ 中的队列程序

让我们举一个例子来说明 C++ 中的队列。

输出

Front element of the queue: 10
Dequeuing elements from the queue: 10 20 30 
Queue is empty.

说明

• 程序首先包含必要的头文件：#include<queue> 用于使用 C++ 标准模板库 (STL) 的队列数据结构，以及 #include<iostream> 用于输入输出操作。
• 在 main() 方法中使用 std::queue 语法声明一个名为 myQueue 的整数队列。这个队列中的元素将由整数表示。
• 接下来，使用 push() 函数将三个整数：10、20 和 30 入队到 myQueue 中。push() 操作遵循“先进先出”(FIFO) 的概念，将元素添加到队列的尾部。
• 该程序使用 myQueue.front() 来显示队列的第一个元素，展示如何访问它而不将其出队。上述方法返回对队列第一个元素的引用。
• 之后，使用 while 循环从队列中出队元素并显示。通过使用 myQueue.empty()，可以确保循环运行，直到队列为空。在循环中，MyQueue.front() 获取队列的第一个元素，并使用 std::cout 显示它。然后通过 myQueue.pop() 的实现将第一个元素从队列中移除。
• 使用 empty() 函数，计算机在将所有元素出队后确定队列是否为空。如果队列中没有元素，则输出“Queue is empty”。否则，打印“Queue is not empty”。

C++ 中的双端队列简介

双端队列，或 C++ 中的 deques，是灵活的数据结构，可在两端进行高效的插入和删除操作。与传统队列不同，双端队列允许元素从前面或后面插入和移除，这使其适用于需要动态数据处理的各种应用程序。对于这些操作，双端队列提供恒定的时间复杂度，使得可以快速访问元素，而不管它们在结构中的位置如何。

C++ 中的标准模板库 (STL) 通过提供一个名为 std::deque 的预制容器来简化双端队列的实现。开发人员可以通过包含头文件在程序中使用此容器及其许多优点。std::deque 容器提供了一个简单的接口来处理 C++ 中的双端队列，它封装了内存管理和重新调整大小的复杂性。

双端队列由一组固定大小的块组成的动态数组构成，每个块可以独立存储多个元素。当添加或删除元素时，这种结构可以动态扩展，并实现有效的内存使用。与向量相比，双端队列在重新调整大小时会创建比向量更小的分块信息。这降低了与重新调整大小操作相关的成本。

与其他顺序容器（如向量）相比，双端队列的高效插入和删除操作是其主要优点之一。

双端队列在两端的操作上保持恒定的时间复杂度，而向量在访问元素时提供恒定的时间复杂度，但在操作的开头添加或删除元素时需要线性时间。这使得双端队列在需要有效地在两端添加或删除元素的场景中特别有用，例如处理算法中的滑动窗口或构建双端队列。

当在 C++ 中处理双端队列时，由于提供了丰富的成员函数和迭代器，程序员可以执行各种操作，例如添加和删除元素、获取特定位置的元素以及遍历双端队列的内容。此外，双端队列提供随机访问，这使得可以使用基于索引的表示法有效地检索元素。开发人员可以通过利用上述特性来创建高效且适应性强的数据结构，以满足其特定需求。

C++ 中的双端队列程序

让我们举一个例子来说明 C++ 中的双端队列。

输出

Elements of the deque: 0 5 10 20 30 
Modified deque after pop operations: 5 10 20 
Element at position 2: 20

说明

• 在此示例中，在 main() 方法中使用 std::deque 语法声明一个包含整数的双端队列，名为 myDeque。此双端队列中的元素将是整数。
• 之后，使用 push_front() 和 push_back() 函数，分别将元素添加到双端队列的前面和后面。在此示例中，按顺序添加了元素：0、5、10、20 和 30。
• 接下来，使用 for 循环遍历双端队列中的每个元素，并使用 std::cout 输出它，以演示双端队列包含的内容。然后，使用 pop_front() 和 pop_back() 函数从双端队列的前面和后面移除元素。结果，元素 0 和 30 被从双端队列中移除。
• 使用与上一个类似的 for 循环，再次显示 pop 操作后的更改的双端队列。元素 5、10 和 20 现在存在于双端队列中。最后，可以使用 at() 函数检索索引 2 处的元素，该函数返回双端队列结构中给定索引处的元素。之后，使用 std::cout 打印索引 2 处的元素值，即 20。

C++ 中队列和双端队列的主要区别

C++ 中的队列和双端队列之间有几个主要区别。一些主要区别如下：

结论

总之，虽然队列和双端队列数据结构都在 C++ 中用于管理元素集合，但它们在满足不同编程需求的方式上有所不同。先进先出 (FIFO) 是队列严格遵循的概念，它使得从尾部进入信息并从头部移除信息更加容易。另一方面，双端队列提供了双向的数据修改方法，并允许在两端进行插入和删除，从而提供了更大的灵活性。双端队列适用于需要两端高效操作的场景，例如实现滑动窗口或通用动态数组，而队列通常用于需要严格保留顺序的场景，例如任务调度或广度优先搜索算法。

此外，这两种数据结构在标准库表示、支持的操作、效率考虑、迭代器的可用性以及使用场景等方面也存在差异。这使得程序员可以根据其应用程序的特定需求灵活地选择最佳解决方案。