Java循环队列原理与用法详解

什么是循环队列

循环队列是一种经典的队列实现方式，它的特点是：队列的头尾相连，形成了一个环形结构。当队列满时，新的数据会从队列头部开始覆盖旧的数据。因此，循环队列在使用过程中，需要记录队列的头部和尾部指针，以便能够正确地判断队列是空还是满，以及在队列中添加、删除元素时，正确地定位到队列的头部和尾部。

基本实现方法

在Java中，循环队列可以通过数组来实现。具体实现方式如下：

public class CircularQueue {
    private Object[] queue;
    private int head;
    private int tail;
    private int size;

    public CircularQueue(int k) {
        queue = new Object[k];
        head = -1;
        tail = -1;
        size = k;
    }

    public boolean enqueue(Object item) {
        if (isFull()) {
            return false;
        } else {
            if (isEmpty()) {
                head = 0;
            }
            tail = (tail + 1) % size;
            queue[tail] = item;
            return true;
        }
    }

    public Object dequeue() {
        if (isEmpty()) {
            return null;
        } else {
            Object item = queue[head];
            if (head == tail) {
                head = -1;
                tail = -1;
            } else {
                head = (head + 1) % size;
            }
            return item;
        }
    }

    public boolean isFull() {
        return head == (tail + 1) % size;
    }

    public boolean isEmpty() {
        return head == -1;
    }
}

上面的代码中，循环队列的核心代码是enqueue和dequeue方法，它们完成了队列的入队和出队操作，其中：

• enqueue方法在尾部添加新元素，如果队列已满，则返回false；
• dequeue方法从头部删除元素，如果队列为空，则返回null；
• isFull方法判断队列是否已满，如果是，则返回true；
• isEmpty方法判断队列是否为空，如果是，则返回true。

使用示例1

CircularQueue queue = new CircularQueue(3);
System.out.println(queue.enqueue("A")); // true
System.out.println(queue.enqueue("B")); // true
System.out.println(queue.enqueue("C")); // true
System.out.println(queue.enqueue("D")); // false
System.out.println(queue.dequeue());   // "A"
System.out.println(queue.enqueue("D")); // true
System.out.println(queue.dequeue());   // "B"
System.out.println(queue.dequeue());   // "C"
System.out.println(queue.dequeue());   // "D"
System.out.println(queue.dequeue());   // null

上面的示例中，我们创建了一个容量为3的循环队列，并依次添加了元素A、B、C。对于D元素，由于队列已满，无法再添加，返回false。接着，我们从头部删除了元素A，并继续添加了元素D。最后，我们依次删除了元素B、C、D，并尝试从空队列中删除元素，返回null。

使用示例2

CircularQueue queue = new CircularQueue(5);
System.out.println(queue.enqueue("A")); // true
System.out.println(queue.enqueue("B")); // true
System.out.println(queue.enqueue("C")); // true
System.out.println(queue.enqueue("D")); // true
System.out.println(queue.dequeue());   // "A"
System.out.println(queue.enqueue("E")); // true
System.out.println(queue.dequeue());   // "B"
System.out.println(queue.dequeue());   // "C"
System.out.println(queue.dequeue());   // "D"
System.out.println(queue.dequeue());   // "E"
System.out.println(queue.dequeue());   // null

上面的示例中，我们创建了一个容量为5的循环队列，并依次添加了元素A、B、C、D。由于队列未满，我们可以继续添加元素E，然后依次删除元素B、C、D、E，并尝试从空队列中删除元素，返回null。

总结

循环队列是一种高效的队列实现方式，适用于大部分的队列场景。在实现循环队列的过程中，需要特别注意头部和尾部指针的使用，以及数组下标取余的边界问题。在使用循环队列时，我们需要根据具体业务需求，选择合适的容量，以便在空间和时间复杂度上达到最优。