Using an Array to Implement a Queue

Our second implementation, ArrayQueue, stores the items in a backing array. We can start with the same representation ArrayStack uses: a backing array and a count.

Now we need to decide how to orient the queue within the array.

Suppose the front of the queue is at index 0 and the back is at the end, at index size - 1. Then enqueue adds at the end of the array, which is $O(1)$ amortized. But dequeue removes the item at index 0, and removing at the front of an array means shifting every remaining item one position to the left: $O(n)$.

So let’s try the other orientation: the back at index 0 and the front at index size - 1. Now dequeue removes at the end of the array, which is $O(1)$. But enqueue has to insert at index 0, which means shifting every item one position to the right: $O(n)$.

Either way, one of the two operations costs $O(n)$ on every call. An array has only one cheap end. ArrayStack never shifts because a stack uses one end. A queue uses both, so one of its operations is always at the expensive end.

So is there a way around this problem? Well, the $O(n)$ cost comes from a limitation we imposed on our array representation: the queue must start at index 0 or the back must be at index 0. If we relax that assumption, we can avoid the $O(n)$ cost.