Designing the ArrayQueue

Let’s look at the details of how the circular array works.

Wrapping with Modulo

We can increment front and back by adding one, but we need to wrap around when we reach the end of the array. One way to do that is an if statement:

back++;
if (back == arr.length) {
  back = 0;
}
// and similarly for front

Another way is to use the remainder operator %:

(back + 1) % arr.length

When back + 1 is less than arr.length, the remainder after dividing by arr.length is back + 1 itself. When back is the last index, back + 1 equals arr.length, and the remainder is 0, so we have wrapped around. The same formula works for front. The if statement is just as good if you prefer it.

What back Points To

In the diagrams so far, back has pointed to the last item in the queue. But what should back be when the queue is empty? If we initialize back to 0, then the first enqueue has to write at index 0 without advancing back, while every later enqueue advances first and then writes. If we initialize back to -1, then every operation that uses back has to check for -1 before doing the arithmetic.

Alternatively, we could have back point to the next free slot after the last item. Then we can initialize back to 0 when the queue is empty. But now back == front is ambiguous. At the start it means the queue is empty:

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

But suppose we enqueue enough items to fill the array. Then back wraps around and points to the same index as front, which now means the queue is full:

┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │
└───┴───┴───┴───┴───┘
  ↑
front,back

So the two indices alone cannot tell an empty queue from a full one. We can avoid this by keeping a size field.

Keeping Track of Size

We have to update size on every enqueue and dequeue. In return, size tells us when the array is full (size == arr.length) and when the queue is empty (size == 0).

We can also compute back from front and size: starting at front and moving size positions around the circle lands on the next free slot.

back == (front + size) % arr.length

For example, suppose front is 4 and size is 3: the queue holds E at index 4, with F and G wrapped around to indices 0 and 1. Then front + size is 7, and 7 % 5 is 2, which is the next free slot:

┌───┬───┬───┬───┬───┐
│ F │ G │ _ │ _ │ E │
└───┴───┴───┴───┴───┘
          ↑       ↑
    (4+3) % 5   front

Growing the Array

When the array is full, we grow it by doubling, as in ArrayStack. The items may be wrapped around the end of the old array, so we cannot just copy each slot to the same index in the new array. Instead we copy the items in order starting from front, wrapping around as needed, and place them in the new array starting at index 0. Then we reset front to 0.

Operations and Complexity

isEmpty(): Check size == 0. This is $O(1)$.

front(): Return the item at index front. This is $O(1)$.

dequeue(): Move front one position around the circle. There is no shifting, so this is $O(1)$.

enqueue(T item): Place the item at the next free slot, growing the array first when it is full. This is amortized $O(1)$, as push is in ArrayStack.