我们可以看到，图中这个队列的大小为 8，当前 head=4，tail=7。当有一个新的元素 a 入队时，我们放入下标为 7 的位置。但这个时候，我们并不把 tail 更新为 8，而是将其在环中后移一位，到下标为 0 的位置。当再有一个元素 b 入队时，我们将 b 放入下标为 0 的位置，然后 tail 加 1 更新为 1。所以，在 a，b 依次入队之后，循环队列中的元素就变成了下面的样子：
队列为空的判断依然是 front == rear，队列满的条件则是 (rear + 1) % capacity = front
你有没有发现，当队列满时，图中的 tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。
/** * 数组实现环形队列 * * @param <E> */ public class ArrayCircleQueue<E> extends AbstractQueue<E> { /** * The queued items */ final E[] items; /** * 队头指针 */ private int front; /** * 队尾指针 */ private int rear; public int capacity() { return items.length; } /** * Creates an ArrayQueue with the given capacity * * @param capacity the capacity of this queue */ public ArrayCircleQueue(Class<E> type, int capacity) { if (capacity <= 0) { throw new IllegalArgumentException(); } this.items = (E[]) Array.newInstance(type, capacity); } @Override public E dequeue() { if (front == rear) { throw new IllegalStateException("Queue empty"); } E item = items[front]; front = (front + 1) % items.length; return item; } @Override public boolean enqueue(E e) { checkNotNull(e); int newRear = (rear + 1) % items.length; if (newRear == front) { throw new IllegalStateException("Queue full"); } items[rear] = e; this.rear = newRear; return true; } @Override public boolean isFull() { return (rear + 1) % items.length == front; } @Override public boolean isEmpty() { return rear == front; } } 推荐阅读1.
2.
3.
4.
5.
6.
7.
8.
原创不易，觉得有用希望随手「在看」「收藏」「转发」三连。