The Circular Array

The questions in this section are about storing a queue in a backing array arr.

Solution

Front at index 0: enqueue is $O (1)$ amortized and dequeue is $O (n)$ , because every remaining item shifts left. Back at index 0: dequeue is $O (1)$ and enqueue is $O (n)$ , because every item shifts right.

Solution

It sets arr[front] to null, moves front one position to the right, and decrements size. No item moves, so it is $O (1)$ .

Exercise

Suppose arr has capacity 5 and the queue holds K, M, W at indices 2, 3, and 4.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ K │ M │ W │
└───┴───┴───┴───┴───┘

Where should the next enqueue place its item, and why?

Solution

At index 0: the back wraps around to the start of the array.

┌───┬───┬───┬───┬───┐
│ _ │ _ │ K │ M │ W │
└───┴───┴───┴───┴───┘
  ↑       ↑
back    front

Indices 0 and 1 are free, so growing would allocate more memory while the array still has empty slots.

Solution

When the queue is empty, back == front. When the array is full, back has wrapped all the way around, so again back == front. The two indices cannot tell empty from full. With size, the queue is empty when size == 0 and full when size == arr.length.

Solution

(front + size) % arr.length. With these values, (3 + 4) % 5 is 2.