Java 循环队列/环形队列的实现流程

循环队列（也称为环形队列）是一种在队列的头部和尾部可以相互转换的队列。它可以避免由于队列尾部占满而导致队列无法继续添加元素的问题。Java 中可以通过数组来实现循环队列，以下是实现流程：

1. 定义一个数组和两个指针

先定义一个数组来存储队列中的元素。定义两个指针，分别指向队列头和队列尾。

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

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

2. 判断队列是否为空或满

• 队列为空：如果队列头和尾指针指向同一个位置，表示队列为空。
• 队列满：如果队列尾指针 + 1 坐标与队列头指针相同时，表示队列已满。

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

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

3. 入队操作

在入队操作之前，需要先判断队列是否已满。如果队列已满，则无法再插入新元素。

public boolean enQueue(int value) {
    if (isFull()) {
        return false;
    }
    if (isEmpty()) {
        head = 0;
    }
    tail = (tail + 1) % size;
    data[tail] = value;
    return true;
}

4. 出队操作

在出队操作之前，需要先判断队列是否为空。如果队列为空，无法进行出队操作。队列不为空时，先将头指针指向下一个位置，并返回原头指针位置存储的元素。

public int deQueue() {
    if (isEmpty()) {
        return -1;
    }
    int value = data[head];
    if (head == tail) {
        head = -1;
        tail = -1;
    } else {
        head = (head + 1) % size;
    }
    return value;
}

示例1

CircularQueue queue = new CircularQueue(3);
queue.enQueue(1); // 队列为 [1]
queue.enQueue(2); // 队列为 [1, 2]
queue.enQueue(3); // 队列为 [1, 2, 3]
queue.enQueue(4); // 返回 false，队列已满
queue.deQueue();  // 返回 1，队列为 [2, 3]
queue.deQueue();  // 返回 2，队列为 [3]
queue.deQueue();  // 返回 3，队列为空
queue.deQueue();  // 返回 -1，队列为空，无法出队

示例2

CircularQueue queue2 = new CircularQueue(5);
queue2.enQueue(2); // 队列为 [2]
queue2.enQueue(5); // 队列为 [2, 5]
queue2.enQueue(9); // 队列为 [2, 5, 9]
queue2.enQueue(1); // 队列为 [2, 5, 9, 1]
queue2.deQueue();  // 返回 2，队列为 [5, 9, 1]
queue2.deQueue();  // 返回 5，队列为 [9, 1]
queue2.deQueue();  // 返回 9，队列为 [1]
queue2.enQueue(3); // 队列为 [1, 3]
queue2.enQueue(6); // 队列为 [1, 3, 6]
queue2.deQueue();  // 返回 1，队列为 [3, 6]

阅读剩余 53%