Tracing the ArrayQueue

Let’s trace the same sequence of operations we ran on LinkedQueue, this time on ArrayQueue, with a few extra steps so the back of the queue wraps around the array.

The ArrayQueue class has no back field. The diagrams below still show a back marker at the next free slot, (front + size) % arr.length, for clarity. The pictures use a capacity-5 array so the wrap happens after only a few operations, and _ marks a null slot.

A fresh queue has front = 0 and size = 0, so back is also 0.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
  ↑
front,back

enqueue(4) places 4 in slot 0 and increments size to 1. The back moves to (0 + 1) % 5 = 1.

┌───┬───┬───┬───┬───┐
│ 4 │ _ │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
  ↑   ↑
front back

enqueue(9) fills slot 1 the same way:

┌───┬───┬───┬───┬───┐
│ 4 │ 9 │ _ │ _ │ _ │
└───┴───┴───┴───┴───┘
  ↑       ↑
front   back

And enqueue(6) fills slot 2:

┌───┬───┬───┬───┬───┐
│ 4 │ 9 │ 6 │ _ │ _ │
└───┴───┴───┴───┴───┘
  ↑           ↑
front       back

Now front() returns 4 and changes nothing.

dequeue() clears slot 0, advances front to (0 + 1) % 5 = 1, and decrements size to 2.

┌───┬───┬───┬───┬───┐
│ _ │ 9 │ 6 │ _ │ _ │
└───┴───┴───┴───┴───┘
      ↑       ↑
    front   back

A second dequeue() removes 9 the same way, leaving front = 2 and size = 1.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ 6 │ _ │ _ │
└───┴───┴───┴───┴───┘
          ↑   ↑
        front back

enqueue(2) computes its slot as (2 + 1) % 5 = 3 and places 2 there.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ 6 │ 2 │ _ │
└───┴───┴───┴───┴───┘
          ↑       ↑
        front   back

enqueue(8) fills slot (2 + 2) % 5 = 4, the last slot of the array. The back is now (2 + 3) % 5 = 0. It has wrapped to the start of the array.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ 6 │ 2 │ 8 │
└───┴───┴───┴───┴───┘
  ↑       ↑
back    front

enqueue(3) places 3 at index 0. There is no special case for the wrap.

┌───┬───┬───┬───┬───┐
│ 3 │ _ │ 6 │ 2 │ 8 │
└───┴───┴───┴───┴───┘
      ↑   ↑
    back front

The queue’s contents, front to back, are 6, 2, 8, 3, but they sit at indices 2, 3, 4, 0. To read the queue in order, you follow (front + i) % arr.length, not the array from left to right.

The array’s capacity stayed at five throughout the trace since grow never ran.