1、概念

环形队列是一个最为简单的数据结构，底层用数组组成，然后逻辑上数组首尾相连。虽然他的结构极为简单，但是用处很大。比如 kafka 的时间轮、基于环形队列做任务触发等。

环形队列

2、实现方法

环形队列有两种实现方式（如果环形队列不考虑首尾的话，只需一个 current index 即可）：

• 1、front、rear 的指针指向首尾，flag 标示为空还是满。当 rear == front 时，flag 为0表示满，flag 1表示空。
• 2、front、rear 的指针指向首尾，rear == front 时表示空，（rear + 1）% maxSize == front 时，表示满（但是此时队尾跟队首必须预留一个元素）。

3、代码实现

方法1:

public class CircleQueue {


    private int[] array;
    private int maxSize;
    private int front;
    private int rear;

    /**
     * flag = 0 表示满，flag = 1 表示空
     */
    private int flag;


    public CircleQueue(int maxSize) {
        this.array = new int[maxSize];
        this.maxSize = maxSize;
        this.front = 0;
        this.rear = 0;
        this.flag = 1;
    }

    public boolean isFull(){
        return rear == front && flag == 0;
    }

    public boolean isEmpty(){
        return rear == front && flag == 1;
    }

    public void offer(int num) throws Exception {
        if(isFull()){
            throw new Exception("队列满了");
        }
        array[rear] = num;
        rear = (rear + 1) % maxSize;
        if(rear == front){
            flag = 0;
        }
    }

    public int poll() throws Exception {
        if(isEmpty()){
            throw new Exception("队列满了");
        }

        int res = array[rear];
        front = (front + 1) % maxSize;
        if(rear == front){
            flag = 1;
        }
        return res;
    }



    public static void main(String[] args) throws Exception {
        CircleQueue circleQueue = new CircleQueue(3);
        circleQueue.offer(1);
        circleQueue.offer(2);
        circleQueue.offer(3);
        circleQueue.offer(4);
    }


}

方法2:

public class CircleQueue {


    private int[] array;
    private int maxSize;
    private int front;
    private int rear;


    public CircleQueue(int maxSize) {
        this.array = new int[maxSize];
        this.maxSize = maxSize;
        this.front = 0;
        this.rear = 0;
    }

    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    public boolean isEmpty(){
        return front == rear;
    }

    public void offer(int num)  throws Exception{
        if(isFull()){
             throw new Exception("队列满了");
        }
        array[rear] = num;
        rear = (rear + 1) % maxSize;
    }

    public int poll()  throws Exception{
        if(isEmpty()){
             throw new Exception("队列空了");
        }

        int res = array[rear];
        front = (front + 1) % maxSize;
        return res;
    }



    public static void main(String[] args) throws Exception {
        CircleQueue circleQueue = new CircleQueue(3);
        circleQueue.offer(1);
        circleQueue.offer(2);
        circleQueue.offer(3);
        circleQueue.offer(4);
    }


}