Implementing enqueue

This is ArrayStack’s push except for the index:

@Override
public void enqueue(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (size == arr.length) {
    grow();  // out of room: make the backing array bigger first
  }
  arr[(front + size) % arr.length] = item;  // place the item in the next free slot
  size++;
}

Notice that we compute the slot after the possible call to grow, because grow changes both arr.length and front.

Here is grow. As we planned in the design, it copies the items in queue order: the item i positions behind the front is at index (front + i) % arr.length, and it goes to index i of the new array.

@SuppressWarnings("unchecked")
private void grow() {
  T[] bigger = (T[]) new Object[arr.length * 2];
  for (int i = 0; i < size; i++) {
    bigger[i] = arr[(front + i) % arr.length];  // the i-th item of the queue, in order
  }
  arr = bigger;
  front = 0;  // the queue now starts at the beginning of the new array
}

Let’s work through an example. Go back to the circular array section, to the moment right after F wrapped around to index 0, and enqueue one more item, G. The queue is now full and wrapped: it starts at index 2, runs to the end of the array, and continues at index 0.

┌───┬───┬───┬───┬───┐
│ F │ G │ C │ D │ E │
└───┴───┴───┴───┴───┘
          ↑
        front

The loop copies C, D, E, F, G, in that order, into the new array.

Here is the state when i is 3. The first three items have been copied from indices 2, 3, and 4. The next read is at (2 + 3) % 5 = 0, which wraps back to the start of the old array to read F.

arr
┌───┬───┬───┬───┬───┐
│ F │ G │ C │ D │ E │
└───┴───┴───┴───┴───┘
          ↑
        front

bigger
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ C │ D │ E │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
              ↑
              i

Two more iterations copy F and G, and the copy is done.

┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ C │ D │ E │ F │ G │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
  ↑
front

The queue is no longer wrapped. With front reset to 0, the next free slot is index size, which is where the enqueue that called grow will put its item.

That completes ArrayQueue.