The Circular Array

Let’s drop the assumption that the front (or the back) of the queue has to be at index 0. Instead we keep a front index that records where the front currently is. Now dequeue clears the slot at front and moves front one position to the right. Nothing shifts, so it is $O (1)$ . enqueue still adds after the last item, which is amortized $O (1)$ as before.

Let’s trace this on an array with room for five items. We enqueue A, B, C, and D:

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

Now dequeue twice (removing A and B) and enqueue E:

┌───┬───┬───┬───┬───┐
│ _ │ _ │ C │ D │ E │
└───┴───┴───┴───┴───┘
          ↑       ↑
        front   back

The queue has moved to the right. Indices 0 and 1 are free, and back is at the last index of the array.

Now we enqueue F. Where does it go? The slot after E does not exist, but the array is not full: two slots are free at the beginning. If we grow the array here, we are allocating more memory while two slots are empty. A program that alternates enqueues and dequeues keeps a small queue, but that queue keeps moving right, so we would grow the array again and again just to hold a few items.

The fix is to use the free slots at the beginning: when back reaches the last index of the array, the next item wraps around to index 0. So F goes into index 0:

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

The order of the queue has not changed: C, then D, E, F. To read it we start at front and wrap past the end of the array back to index 0. We are treating the array as a circle. An array used this way is called a circular array (you may also see the name ring buffer).

The same wrapping applies to front. Dequeue C and D, and front reaches the last index:

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

Dequeue E, and front wraps around to 0, landing on the same slot as back:

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