如图,判断循环队列是否已满是根据队首front和队尾tail的关系。如果数组的最后一个位置已有元素,但是队首前面依然有空格也不表示队列已满。需要注意的是,我们需要空余出一个位置来,以图中为例,此时“tail+1= =front”,如果继续填入元素,那么tail==front,和判断队列是否为空——“front= =tail”就冲突了。因此当“tail+1= =front”时,我们就不继续做入队操作,而是要扩充队列长度。 对元素的队尾我们要判断的是它和队首的相对位置,因此“(tail+1)% c”如果等于队首就说明队列已满。

入队

我们来看一下入队操作。需要先判断是否已满。如果队尾+1等于队首,则扩容操作resize(getCapacity()*2);扩容后再入队,并且队尾指向新的位置。

if ((tail + 1) % data.length == front) {
    resize(this.getCapacity() * 2);
}
data[tail] = e;
tail = (tail + 1) % data.length;
size++;

扩容

关于扩容操作,复制数组内的对象时与一般的队列有所不同,即 newData[i] = data[(front + i) % data.length];“front + i”中的 i 是队列的第几个元素,(front + i) % data.length就得到了在数组中的实际位置。

private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newData[i] = data[(front + i) % data.length];
    }
    data = newData;
    front = 0;
    tail = size;
}

出队

先判断队列是否为空,然后保存队首元素。更新队首front和队列长度size后,要判断是否需要缩容。

public E dequeue() {
    if (isEmpty()) {
        throw new IllegalArgumentException("Connot dequeue from a empty queue.");
    }
    E ret = data[front];
    data[front] = null;
    front = (front + 1) % data.length;
    size--;

    if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
        resize(getCapacity() / 2);
    }
    return ret;
}