DS：循环队列的实现

循环队列是一种特殊的队列实现方式，它通过将队头和队尾指针循环利用，实现有效的空间利用。这种数据结构非常适合用于处理有固定长度的队列问题，例如任务调度、数据缓冲等场景。

循环队列的结构

一个循环队列可以用数组来实现，在数组中维护两个指针：front指向队头，rear指向队尾。与普通队列不同，循环队列的特色在于，当队尾指针到达数组末尾时，如果有空余空间，它可以回到数组开头，从而形成一种“循环”。

循环队列的基本操作

1. 入队（Enqueue）: 将元素添加到队尾。需要检查队列是否已满。
2. 出队（Dequeue）: 从队头删除元素。需要检查队列是否为空。
3. 获取队头元素（Front）: 查看队头元素但不删除它。
4. 判断队列是否为空（IsEmpty）: 判断队列是否没有元素。
5. 判断队列是否已满（IsFull）: 判断队列是否已到最大容量。

循环队列的实现

以下是一个用Python实现的循环队列的示例代码：

class CircularQueue:
    def __init__(self, size):
        self.size = size + 1  # 因为我们要留一个空位来区分满和空
        self.queue = [None] * self.size
        self.front = 0
        self.rear = 0

    def is_empty(self):
        return self.front == self.rear

    def is_full(self):
        return (self.rear + 1) % self.size == self.front

    def enqueue(self, value):
        if self.is_full():
            print("队列已满，无法添加元素")
            return
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.size

    def dequeue(self):
        if self.is_empty():
            print("队列为空，无法删除元素")
            return None
        value = self.queue[self.front]
        self.front = (self.front + 1) % self.size
        return value

    def front_element(self):
        if self.is_empty():
            print("队列为空，无法获取队头元素")
            return None
        return self.queue[self.front]

    def display(self):
        if self.is_empty():
            print("队列为空")
            return
        idx = self.front
        elements = []
        while idx != self.rear:
            elements.append(self.queue[idx])
            idx = (idx + 1) % self.size
        print("队列元素:", elements)


# 测试循环队列
if __name__ == "__main__":
    circular_queue = CircularQueue(5)

    circular_queue.enqueue(1)
    circular_queue.enqueue(2)
    circular_queue.enqueue(3)
    circular_queue.enqueue(4)
    circular_queue.enqueue(5)
    circular_queue.enqueue(6)  # 测试队列已满

    circular_queue.display()

    print("出队元素:", circular_queue.dequeue())
    print("队头元素:", circular_queue.front_element())

    circular_queue.display()

    circular_queue.enqueue(6)  # 测试出队后入队
    circular_queue.display()

代码解释

1. 初始化方法：创建了一个长度为size + 1的数组，以便提供一个空位来区分队列是满还是空。
2. 判断队列是否为空：通过比较front和rear指针来判断。
3. 判断队列是否已满：通过判断(rear + 1) % size是否等于front来判断队列是否已满。
4. 入队操作：添加元素时，会在rear指向的位置放置新元素，并更新rear指针。
5. 出队操作：从front指向的位置取出元素，并更新front指针。
6. 显示队列元素：从front到rear遍历数组，打印出当前队列的元素。

这个实现展示了循环队列的基本操作，也可以根据需要扩展更多功能，比如动态调整队列大小等。在实际应用中，循环队列常用于资源管理和任务调度等场景。