C++ 中的队列数组实现

引言

队列是计算机科学中用于以 FIFO（先进先出）方式管理数据的基本数据结构。它们通常用于需要按接收顺序执行任务的场景，例如作业调度、广度优先搜索算法和操作系统中的请求处理。实现队列最直接的方法之一是使用数组。

数组实现

使用数组实现队列是一种简单有效的方法。在此实现中，我们使用数组来存储队列的元素，并维护两个指针：一个指向队列的头部，另一个指向尾部。以下是我们可以使用数组实现上述基本操作的方法

• 入队

增加尾指针。

在尾指针指示的索引处添加新元素。

• 出队

返回头指针指示的索引处的元素。

增加头指针。

• 头

返回头指针指示的索引处的元素。

• 尾

返回尾指针指示的索引处的元素。

• isEmpty

检查头指针是否等于尾指针。如果它们相等，则队列为空。

• 已满

检查尾指针是否等于数组大小减一（表示数组已满）。

实施

说明

• 程序定义了一个宏 SIZE 来指定队列的最大大小，并声明了一个 Queue 类来封装队列数据结构。
• 该类包括私有成员变量 front、rear、capacity 和一个动态整数数组 array，用于存储队列元素。
• 构造函数 Queue(int size = SIZE) 使用指定的大小（如果未提供，则使用默认大小）初始化队列。
• 它将 front 和 rear 设置为 -1 以指示空队列，并为数组动态分配内存。
• 析构函数 ~Queue() 在对象超出范围时释放为数组动态分配的内存。
• Queue 类提供了用于队列操作的成员函数。
• 这些函数包括 isEmpty() 用于检查队列是否为空，isFull() 用于检查队列是否已满，enqueue(int item) 用于向队列添加元素，dequeue() 用于从队列中删除元素，以及 peek() 用于返回队列头部的元素而不删除它。
• 在 main() 函数中，创建了一个名为 queue 的 Queue 类实例。使用 enqueue() 方法将元素（10、20、30）入队到队列中。
• 使用 dequeue() 方法将第一个元素出队并打印。使用 peek() 方法打印队列的头部元素。

程序输出

复杂度分析

让我们分析队列的数组实现中每个操作的时间复杂度

入队操作 (enqueue)

• 时间复杂度：O(1)
• 解释：在入队操作中，我们只是在队列的尾部插入一个元素。由于我们跟踪尾部索引，因此在尾部插入元素需要常数时间，与队列中已存在的元素数量无关。

出队操作 (dequeue)

• 时间复杂度：O(1)
• 解释：与入队类似，出队操作也需要常数时间。我们只是从队列的头部删除元素。通过跟踪头部索引，我们可以在常数时间内出队。

查看操作 (peek)

• 时间复杂度：O(1)
• 解释：查看操作返回队列头部的元素。由于我们始终跟踪头部索引，因此访问头部元素需要常数时间。

isEmpty 操作 (isEmpty)

• 时间复杂度：O(1)
• 解释：检查队列是否为空涉及对 front 和 rear 索引的简单比较。因此，它需要常数时间。

isFull 操作 (isFull)

• 时间复杂度：O(1)
• 解释：与 isEmpty 类似，检查队列是否已满也涉及对 rear 索引与数组最大大小的简单比较。因此，它需要常数时间。

数组实现的优点

效率：队列的数组实现为大多数操作（如入队、出队、头和尾）提供了常数时间复杂度 O(1)。

简单性：实现简单明了，易于理解，使其成为教育目的和小型应用的理想选择。

内存效率：它线性消耗内存，不像链表实现那样遭受内存碎片问题。

局限性和注意事项

固定大小：在数组实现中，队列的大小是固定的。一旦数组满了，除非元素出队以释放空间，否则进一步的入队操作将失败。

动态调整大小：为了克服固定大小的限制，可以采用动态调整大小技术，例如在数组满时将其大小加倍。但是，如果数组需要频繁调整大小，这可能会导致偶尔耗时的操作。

空间浪费：如果数组的大小明显大于队列中的元素数量，可能会导致空间浪费。

结论

队列的数组实现提供了一种简单有效的方法来以 FIFO 方式管理数据，基本操作的时间复杂度为常数。其优点在于效率、简单性和线性内存消耗。

但是，需要考虑固定大小和潜在空间浪费等限制，以及动态调整大小等可能的解决方案，以实现更灵活的用法。总的来说，基于数组的队列为需要 FIFO 数据管理的各种应用程序提供了一个实用的选择。