5. 如何在Java中实现一个循环队列（Circular Queue）？

1. 什么是循环队列（Circular Queue）？

循环队列（Circular Queue） 是一种特殊的队列，它在逻辑上将队列的末尾连接到队列的开头，从而形成一个环形结构。这种设计使得在使用固定大小的数组实现队列时，能够更高效地利用空间，避免浪费。当队列的尾部到达数组的末尾时，如果前面有空闲位置，新的元素可以插入到数组的开头部分。

循环队列需要维护两个指针：

• front：指向队列的第一个元素。
• rear：指向队列的最后一个元素。

队列的状态可以通过 front 和 rear 的位置关系来判断：

• 当 front == rear 且 isEmpty == true 时，表示队列为空。
• 当 (rear + 1) % capacity == front 时，表示队列已满。

2. 在 Java 中实现循环队列

下面是一个使用数组实现的循环队列的示例代码。

2.1 循环队列的实现

public class CircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int k) {
        capacity = k + 1; // 预留一个空位来区分队列满和空的状态
        data = new int[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }

    // 入队操作
    public boolean enqueue(int value) {
        if (isFull()) {
            return false;
        }
        data[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    // 出队操作
    public boolean dequeue() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    // 获取队首元素
    public int front() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return data[front];
    }

    // 获取队尾元素
    public int rear() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty");
        }
        return data[(rear - 1 + capacity) % capacity];
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 判断队列是否已满
    public boolean isFull() {
        return size == capacity - 1;
    }
}

2.2 循环队列的关键点

• 容量管理：为了区分队列满和队列空的情况，实际使用的数组大小比实际所需的队列容量多一个元素。
• 循环特性：通过 (index + 1) % capacity 来实现循环，当指针到达数组末尾时，能够自动回绕到数组的开头。

2.3 使用示例

下面是如何使用上述 CircularQueue 的示例代码：

public class CircularQueueExample {

    public static void main(String[] args) {
        CircularQueue queue = new CircularQueue(5); // 队列容量为5

        // 入队操作
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);

        System.out.println("Front element: " + queue.front());
        System.out.println("Rear element: " + queue.rear());

        // 尝试再入队一个元素（应该失败，因为队列已满）
        boolean success = queue.enqueue(60);
        System.out.println("Attempt to enqueue another element: " + (success ? "Success" : "Fail"));

        // 出队操作
        queue.dequeue();
        queue.dequeue();

        System.out.println("Front element after two dequeues: " + queue.front());
        System.out.println("Rear element after two dequeues: " + queue.rear());

        // 再次入队操作
        queue.enqueue(60);
        System.out.println("Rear element after enqueueing 60: " + queue.rear());
    }
}

输出示例：

Front element: 10
Rear element: 50
Attempt to enqueue another element: Fail
Front element after two dequeues: 30
Rear element after two dequeues: 50
Rear element after enqueueing 60: 60

3. 循环队列的优缺点

3.1 优点

• 空间利用率高：循环队列能够充分利用数组的空间，避免普通队列实现中的空间浪费问题。
• 高效的入队和出队操作：入队和出队操作的时间复杂度为 O(1)，适合频繁插入和删除的场景。

3.2 缺点

• 容量固定：如果数组容量设定过小，可能会在高峰期频繁发生队列已满的情况，需要手动扩容。
• 复杂性增加：循环队列的实现较普通队列复杂，需要注意指针的循环管理以及队列满和空的判断条件。

4. 总结

循环队列是一种高效的队列实现方式，通过数组实现的循环结构，可以充分利用空间并且在队列的两端进行高效的插入和删除操作。在实际开发中，如果队列的容量是固定的且队列元素会频繁入队和出队，循环队列是一个非常适合的选择。Java 中可以通过管理两个指针（front 和 rear）并结合数组来实现一个简单而有效的循环队列。