编辑“︁循环队列”︁

{{DISPLAYTITLE:循环队列}}

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

== 基本概念 ==

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

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

== 工作原理 ==

循环队列使用两个指针：
* '''front'''：指向队列第一个元素
* '''rear'''：指向队列最后一个元素的下一个位置

<mermaid>
graph LR
    subgraph 循环队列
    A[0] --> B[1]
    B --> C[2]
    C --> D[3]
    D --> E[4]
    E -->|循环| A
    end
    style A fill:#f9f,stroke:#333
    style E fill:#f9f,stroke:#333
</mermaid>

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

== 实现示例 ==

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

<syntaxhighlight lang="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])
</syntaxhighlight>

=== 示例操作 ===
<syntaxhighlight lang="python">
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)  # 队列已满
</syntaxhighlight>

== 数学表示 ==

循环队列的指针移动可以通过模运算表示：
<math>
\text{rear} = (\text{rear} + 1) \mod \text{size}
</math>
<math>
\text{front} = (\text{front} + 1) \mod \text{size}
</math>

== 实际应用 ==

循环队列在计算机系统中有广泛应用：

1. '''CPU任务调度'''：操作系统使用循环队列管理就绪进程
2. '''内存管理'''：循环缓冲区用于数据流处理
3. '''网络通信'''：数据包缓冲区常采用循环队列实现
4. '''打印机缓冲'''：管理多个打印任务的执行顺序
5. '''多媒体处理'''：音频/视频流的缓冲处理

== 复杂度分析 ==

{| class="wikitable"
|-
! 操作 !! 时间复杂度 !! 空间复杂度
|-
| 入队(enqueue) || O(1) || O(1)
|-
| 出队(dequeue) || O(1) || O(1)
|-
| 访问队首 || O(1) || O(1)
|-
| 判空/判满 || O(1) || O(1)
|}

== 常见问题 ==

=== 如何区分队列空和队列满？ ===
常用三种解决方案：
1. 牺牲一个存储单元（如上文实现）
2. 使用计数器记录元素个数
3. 使用标志位记录最后一次操作是入队还是出队

=== 动态扩容问题 ===
循环队列通常大小固定，要实现动态扩容需要：
1. 创建更大的新数组
2. 将原队列元素按顺序复制到新数组
3. 调整front和rear指针

== 扩展阅读 ==

* 双端循环队列（Deque）的实现
* 优先循环队列（Priority Circular Queue）
* 多线程环境下的线程安全循环队列

循环队列是基础但重要的数据结构，理解其原理和实现有助于开发高效、稳定的系统程序。建议读者通过实际编码练习来加深理解。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]