数据结构中的循环队列

为什么引入循环队列的概念？

在队列的数组实现中存在一个限制。如果队尾指针到达队列的末尾，那么队列开头可能存在一些未被利用的空闲空间。为了克服这些限制，引入了循环队列的概念。

从上图可以看出，队尾指向队列的最后一个位置，而队头指向的不是第 0 个位置。在上面的数组中，只有两个元素，其他三个位置是空的。队尾指向队列的最后一个位置；如果我们尝试插入元素，它会显示队列中没有空闲空间。有一个解决方案可以避免这种内存空间的浪费，那就是移动所有元素到左边，并相应地调整队头和队尾。这不是一个实际上好的方法，因为移动所有元素会消耗大量时间。避免内存浪费的有效方法是使用循环队列数据结构。

什么是循环队列？

循环队列与线性队列相似，因为它也基于 FIFO（先进先出）原则，不同之处在于循环队列的最后一个位置连接到第一个位置，形成一个圆。它也被称为环形缓冲区。

循环队列上的操作

在循环队列上可以执行的操作如下：

• 队头 (Front): 用于从队列中获取队头元素。
• 队尾 (Rear): 用于从队列中获取队尾元素。
• 入队 (enQueue(value)): 此函数用于在队列中插入新值。新元素始终从队尾插入。
• 出队 (deQueue()): 此函数从队列中删除一个元素。队列中的删除操作始终从队头进行。

循环队列的应用

循环队列可用于以下场景：

• 内存管理：循环队列提供内存管理。正如我们已经看到的，在线性队列中，内存管理效率不高。但在循环队列的情况下，通过将元素放置在未使用过的位置来高效地管理内存。
• CPU 调度：操作系统也使用循环队列来插入进程然后执行它们。
• 交通系统：在计算机控制交通系统中，交通灯是循环队列的最佳示例之一。交通灯的每个灯都会在一个时间间隔后依次亮起。例如，红灯亮一分钟，然后黄灯亮一分钟，然后绿灯。绿灯之后，红灯亮起。

入队操作

入队操作的步骤如下：

• 首先，我们将检查队列是否已满。
• 最初，队头和队尾设置为 -1。当我们向队列中插入第一个元素时，队头和队尾都设置为 0。
• 当我们插入一个新元素时，队尾会递增，即rear=rear+1。

插入元素的场景

有两种队列不满的场景：

• 如果 rear != max - 1，则 rear 将增加到 mod(maxsize)，并且新值将插入到队列的队尾。
• 如果 front != 0 且 rear = max - 1，这意味着队列未满，然后将 rear 的值设置为 0 并在那里插入新元素。

有两种情况无法插入元素：

• 当 front ==0 && rear = max-1 时，这意味着队头位于队列的第一个位置，而队尾位于队列的最后一个位置。
• front== rear + 1;

向循环队列中插入元素的算法

步骤 1：如果 (REAR+1)%MAX = FRONT
打印“溢出”
转到步骤 4
[IF 结束]

步骤 2：如果 FRONT = -1 且 REAR = -1
设置 FRONT = REAR = 0
否则，如果 REAR = MAX - 1 且 FRONT ! = 0
设置 REAR = 0
否则
设置 REAR = (REAR + 1) % MAX
[IF 结束]

步骤 3：设置 QUEUE[REAR] = VAL

步骤 4：退出

出队操作

出队操作的步骤如下：

• 首先，我们检查队列是否为空。如果队列为空，则无法执行出队操作。
• 删除元素时，front 的值会减 1。
• 如果只剩一个要删除的元素，则 front 和 rear 会重置为 -1。

从循环队列中删除元素的算法

步骤 1：如果 FRONT = -1
打印“下溢”
转到步骤 4
[IF 结束]

步骤 2：设置 VAL = QUEUE[FRONT]

步骤 3：如果 FRONT = REAR
设置 FRONT = REAR = -1
否则
如果 FRONT = MAX -1
设置 FRONT = 0
否则
设置 FRONT = FRONT + 1
[IF 结束]
[IF 结束]

步骤 4：退出

让我们通过图示来理解入队和出队操作。

使用数组实现循环队列

输出

使用链表实现循环队列

我们知道链表是一种线性数据结构，它存储两个部分，即数据部分和地址部分，其中地址部分包含下一个节点的地址。这里，链表用于实现循环队列，因此链表遵循队列的属性。当我们使用链表实现循环队列时，入队和出队操作都花费O(1)时间。

输出