JAVA如何实现循环队列

循环队列是一种特殊的队列,它的尾部连接到头部,形成一个循环体。当队列满时,新元素会替换队头元素。

循环队列可以通过数组实现,关键就是控制好队头指针front和队尾指针rear,具体实现如下:

public class CircleQueue {
    private int[] arr;      // 数组
    private int front;      // 队头指针
    private int rear;       // 队尾指针
    private int size;       // 当前队列大小
    
    public CircleQueue(int capacity) {
        arr = new int[capacity];
        front = 0;
        rear = 0;
        size = 0;
    }
    
    // 入队操作
    public void enQueue(int element) {
        if (isFull()) {
            System.out.println("Queue is full!");
            return;
        }
        arr[rear] = element;
        rear = (rear + 1) % arr.length;   // circulating rear pointer 
        size++;
    }  
    
    // 出队操作
    public int deQueue() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        int element = arr[front];
        front = (front + 1) % arr.length;   // circulating front pointer
        size--;
        return element;
    }
    
    // ...
}

关键点是使用数组的模(%操作)来循环移动front和rear指针,这确保了队列在数组范围内循环使用。

当队列满时,front == rear,此时入队会覆盖front指向的元素,实现循环使用数组空间。

通过控制好指针和使用模运算,我们实现了基于数组的循环队列。

循环队列相比普通队列的主要优点是在大小受限的情况下,可以循环使用空间,不会出现“队列满”的情况。这在需要固定长度的队列情况下比较实用。