循环队列

循环队列：数组队列的优化与实现

循环队列是对数组实现的线性队列的改进，通过 “逻辑上环化” 数组，解决了普通队列因头尾指针单向移动导致的 “假满” 问题，提高了数组空间的利用率。本文详细解析循环队列的原理、判断条件及实现方式。

普通队列的 “假满” 问题

普通队列（基于数组）的头尾指针（front、rear）只能单向移动：

• 入队时 rear 后移，出队时 front 后移。
• 当 rear 达到数组末尾（rear = capacity-1）时，即使 front 前有空闲空间，也无法继续入队（称为 “假满”）。

例如：

• 数组容量为 5，入队 [A,B,C,D] 后，rear=3，front=0。
• 出队 A 和 B 后，front=2，rear=3（此时数组前 2 个位置空闲）。
• 若再入队 E，rear=4（已满）；若继续入队 F，则因 rear 无法移动导致 “假满”，但实际 front 前有空间。

循环队列的核心思想

循环队列通过逻辑上环化数组（即 rear 到达数组末尾后，重新从 0 开始）解决假满问题：

• 数组的首尾在逻辑上相连（形成环形）。
• rear 和 front 移动时，通过取模运算（% capacity）实现 “循环”。

循环队列的关键判断条件

为区分 “队空” 和 “队满”，循环队列通常浪费一个空间（即数组容量为 capacity 时，最多存储 capacity-1 个元素）。

1. 队空条件

• 当 front == rear 时，队列为空。
• 含义：头尾指针重合，无元素可出队。

2. 队满条件

• 当 (rear + 1) % capacity == front 时，队列已满。
• 含义：rear 向后移动一位（取模后）与 front 重合，此时剩余 1 个空间未使用（用于区分队空）。

3. 元素个数计算

• 队列中元素数量 = (rear - front + capacity) % capacity。
• 解释：通过 +capacity 避免 rear < front 时出现负数（如 rear=1，front=3，capacity=5 时，(1-3+5)%5=3，即 3 个元素）。

循环队列的实现（Java）

public class CircularQueue {
    private int[] queue;   // 存储元素的数组
    private int front;     // 队头指针（指向第一个元素）
    private int rear;      // 队尾指针（指向最后一个元素的下一位）
    private int capacity;  // 数组容量（实际最大存储 capacity-1 个元素）

    // 初始化队列
    public CircularQueue(int capacity) {
        this.capacity = capacity;
        queue = new int[capacity];
        front = 0;
        rear = 0;
    }

    // 入队
    public boolean enqueue(int value) {
        if (isFull()) {
            System.out.println("队列已满，无法入队");
            return false;
        }
        queue[rear] = value;       // 存入元素
        rear = (rear + 1) % capacity;  // 队尾指针后移（循环）
        return true;
    }

    // 出队
    public Integer dequeue() {
        if (isEmpty()) {
            System.out.println("队列为空，无法出队");
            return null;
        }
        int value = queue[front];   // 取出队头元素
        front = (front + 1) % capacity; // 队头指针后移（循环）
        return value;
    }

    // 获取队头元素
    public Integer peek() {
        if (isEmpty()) {
            return null;
        }
        return queue[front];
    }

    // 判断队空
    public boolean isEmpty() {
        return front == rear;
    }

    // 判断队满
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    // 获取元素个数
    public int size() {
        return (rear - front + capacity) % capacity;
    }

    // 测试
    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5); // 容量5，最多存4个元素
        cq.enqueue(1);
        cq.enqueue(2);
        cq.enqueue(3);
        cq.enqueue(4);
        System.out.println("入队4个元素后是否满：" + cq.isFull()); // true

        System.out.println("出队：" + cq.dequeue()); // 1
        System.out.println("出队后元素个数：" + cq.size()); // 3

        cq.enqueue(5);
        System.out.println("入队5后元素个数：" + cq.size()); // 4（未超上限）
        System.out.println("队头元素：" + cq.peek()); // 2
    }
}

输出结果：

入队4个元素后是否满：true
出队：1
出队后元素个数：3
入队5后元素个数：4
队头元素：2

循环队列的优缺点

优点

• 空间利用率高：解决了普通队列的 “假满” 问题，充分利用数组空间。
• 操作高效：入队、出队、判断空满的时间复杂度均为 O (1)。

缺点

• 浪费一个空间：为区分空满，需预留 1 个空间（可通过额外变量记录元素个数解决，但增加复杂度）。
• 容量固定：基于数组实现，初始化后容量不可动态扩展（需重建数组扩容）。

适用场景

• 已知最大元素数量的场景（如固定大小的缓冲区、线程池任务队列）。
• 对效率要求高，需频繁入队出队的场景（如生产者 - 消费者模型）。

总结

循环队列通过逻辑上环化数组，有效解决了普通队列的假满问题，是数组队列的高效优化版本。其核心在于通过 front 和 rear 指针的循环移动，结合 (rear+1)%capacity == front 判断队满，front == rear 判断队空，实现了 O (1) 时间复杂度的基本操作。尽管浪费一个空间，但在固定容量场景中，其高效性和简洁性使其成为优选方案