规定：

head 指向队列第一个元素；
tail 指向队列最后一个元素的后一个位置。

public class ArrayCircularBlockQueue<E> {
    /**
     * 存储数据的数组
     */
    private final Object[] items;
    /**
     * 队列大小
     */
    private final int capacity;
    /**
     * 队列头下标
     */
    private int head;
    /**
     * 队列尾下标
     */
    private int tail;

    public ArrayCircularBlockQueue(int capacity) {
        this.capacity = capacity;
        this.items = new Object[capacity];
    }

    public boolean enqueue(E data) {
        boolean full = (tail + 1) % capacity == head;
        // 队满
        if (full) {
            return false;
        }
        else {
            items[tail] = data;
            // 队尾指针后移
            tail = (tail + 1) % capacity;
            return true;
        }
    }

    public E dequeue() {
        // 队空
        if (head == tail) {
            return null;
        }
        else {
            // 取出队头数据
            E item = (E) items[head];
            // 队头指针后移
            head = (head + 1) % capacity;
            return item;
        }
    }
}

环形队列.gif

几个问题

1. 为什么计算指针的时候要取模capacity？

如图所示capacity = 8，下标只有0到7，取模的含义实际上就是求余数，余数就是除不尽被除数的剩余，永远小于被除数。

比如 a / 10，那么余数永远在0-9之间，余数=0表示整除、刚开始。

如此，以尾指针为例，

• 开始的时候下标为0，也就相当于整除了，0除以8，余数为0；
• 入队一个数据，下标变成1，1除以8，余数为1；
• 出队一些数据，入队一些数据之后，当tail从7往0移动的时候，7+1=8，除以capacity余数刚好为0。

即：

取模capacity，表示已经走过 n 个完整的周期，现在是第 n+1 个周期的第几步。

可以类比时间，每天 24 小时，现在是第几天的 2 点？

2. 为什么要空一个？

因为当 head = tail 时，不知道是处于队空还是队满，无法识别。
所以用 (tail + 1) % capacity 来表示如果再增加入队一个，就像时间一样，head已经1时，tail 如果此时处于24时，(tail +1)%24 =1。