Using an Array to Implement a Deque

Now we try the array implementation. The queue chapter already showed the problem: if we force the front of the structure to stay at index 0, removing from the front shifts everything.

For a deque, the problem is even worse. A deque adds and removes at both ends, so whichever end we fix at index 0 has to shift. A deque needs both ends to be cheap.

The circular array solves this the same way it did for the queue: do not force the first item to stay at index 0. Keep a front index, store the deque as a run of items around the circle, and let either end move.

A queue only needs to move front forward and add at the computed back slot. A deque also needs to move front backward for addFirst, and it needs to find the current last item for getLast and removeLast.

addFirst writes here
          ↓
┌───┬───┬───┬───┬───┐
│ C │ _ │ _ │ A │ B │
└───┴───┴───┴───┴───┘
              ↑
            front

In this picture, the first item is A at index 3, then B at index 4, then C at index 0. The deque contents are A, B, C, even though the array order is C, A, B if we read left to right.

The front index marks where the first item is stored, index 3. An addFirst does not shift anything; it just moves front one slot backward, to index 2, and writes the new item there.

addLast writes into the free slot just past the last item, as enqueue does in ArrayQueue.