循环队列

循环队列（Circular Queue）是队列的一种特殊实现形式，它通过将线性存储空间的收尾相连来解决普通队列的"假溢出"问题，显著提高了存储空间的利用率。本文将详细介绍循环队列的工作原理、实现方式以及实际应用场景。

基本概念[编辑 | 编辑源代码]

循环队列是一种遵循先进先出（FIFO）原则的数据结构，与普通队列的主要区别在于其存储空间的循环利用特性。当队列尾部指针到达存储空间末尾时，会从存储空间的起始位置重新开始使用空间。

核心特点[编辑 | 编辑源代码]

解决普通顺序队列的"假溢出"问题（队列实际未满但无法插入新元素）
通过模运算实现指针循环
需要区分队列空和队列满的判定条件
空间利用率可达100%

工作原理[编辑 | 编辑源代码]

循环队列使用两个指针：

front：指向队列第一个元素
rear：指向队列最后一个元素的下一个位置

关键操作[编辑 | 编辑源代码]

入队（enqueue）：在rear位置添加元素，rear = (rear + 1) % size
出队（dequeue）：移除front位置元素，front = (front + 1) % size
判空：front == rear
判满：(rear + 1) % size == front

实现示例[编辑 | 编辑源代码]

以下是Python实现的循环队列示例：

class CircularQueue:
    def __init__(self, size):
        self.size = size
        self.queue = [None] * size
        self.front = self.rear = -1
    
    def enqueue(self, item):
        if (self.rear + 1) % self.size == self.front:
            print("队列已满")
        elif self.front == -1:  # 空队列
            self.front = self.rear = 0
            self.queue[self.rear] = item
        else:
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = item
    
    def dequeue(self):
        if self.front == -1:
            print("队列为空")
            return None
        elif self.front == self.rear:  # 最后一个元素
            temp = self.queue[self.front]
            self.front = self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size
            return temp
    
    def display(self):
        if self.front == -1:
            print("队列为空")
        elif self.rear >= self.front:
            print("队列元素:", self.queue[self.front:self.rear+1])
        else:
            print("队列元素:", self.queue[self.front:] + self.queue[:self.rear+1])

示例操作[编辑 | 编辑源代码]

cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
cq.enqueue(30)
cq.display()  # 输出: 队列元素: [10, 20, 30]
cq.dequeue()
cq.display()  # 输出: 队列元素: [20, 30]
cq.enqueue(40)
cq.enqueue(50)
cq.enqueue(60)  # 队列已满