Solution: Tracing MaxQueue

Let’s trace! We use the sequence from the problem statement: enqueue(7), enqueue(2), enqueue(5), enqueue(1), enqueue(4), and then three calls to dequeue(). The diagrams below show the candidate deque, and I describe the real queue items in the text.

The five enqueues build the candidate list we walked through when keeping the candidates: enqueue(5) evicts 2 from the back of candidates, and enqueue(4) evicts 1. After enqueue(4), the real queue is 7, 2, 5, 1, 4, and candidates holds 7, 5, 4:

┌───┬───┬───┐
│ 7 │ 5 │ 4 │
└───┴───┴───┘
  ▲       ▲
first   last

Now the first dequeue(). The 7 leaves from items (real queue 2, 5, 1, 4), and it is the front of candidates, so the front candidate leaves too:

┌───┬───┐
│ 5 │ 4 │
└───┴───┘
  ▲   ▲
first last

getMax() returns 5, the front of candidates, without looking at the four values in the queue.

The second dequeue() removes 2 (real queue 5, 1, 4). It is not the front of candidates, so the candidates do not change:

┌───┬───┐
│ 5 │ 4 │
└───┴───┘
  ▲   ▲
first last

The third dequeue() removes 5 (real queue 1, 4). This time the removed queue item is also the front of candidates, so the front candidate leaves:

┌───┐
│ 4 │
└───┘
  ▲
first, last

Now getMax() returns 4.