Solution: Cost

What is the complexity of the MaxQueue operations?

front, getMax, and isEmpty each do a check and at most one deque read, so they are $O (1)$ .
dequeue does a check, one removal from items, and at most one removal from candidates, so it is $O (1)$ too.
The expensive operation is enqueue, because its while loop can remove many candidates at once. If the queue holds 9, 8, 7, 6 and we enqueue 10, all four candidates leave. So a single enqueue can cost $O (n)$ .

Counting per call gives a bound of $O (n)$ on enqueue, and that is a true bound, but it is not the whole story. The while loop in enqueue is the monotonic stack’s push from the stack chapter’s practice problems, and the same argument applies: an expensive enqueue evicts candidates that earlier, cheap enqueues added, and a candidate is evicted at most once. To make that precise, we count the deque operations per item instead of per call, the way we did for the queue with two stacks.

Follow one item from enqueue to dequeue. It is added to items once and removed from items once. It is added to candidates once, and removed from candidates at most once, either from the back when a larger item arrives or from the front when it leaves the queue as the maximum. So each item is responsible for at most four deque operations, no matter how many calls happen around it.

The rest is the sum from the queue with two stacks. Over $m$ operations, $n$ of them enqueues, each call does a fixed amount $c$ of its own work, and the items add at most $4 n$ deque operations in total. Every item is enqueued by one of the calls, so $n \leq m$ and the total is at most $(c + 4) m$ . So each operation is amortized $O (1)$ . Check it against the trace. There $m = 8$ and $n = 5$ . The five enqueues add 5 items to items and 5 to candidates. The three dequeues remove 3 items from items. Four values leave candidates: 2 and 1 from the back when 5 and 4 arrive, then 7 and 5 from the front when they are dequeued. That is $5 + 5 + 3 + 4 = 17$ deque operations, under the bound of $4 n = 20$ .

The space is $O (n)$ in the worst case, where $n$ is the number of items currently in the queue. If the values are decreasing, every value remains a candidate. For the queue 9, 8, 7, 6 the candidate deque holds all four:

┌───┬───┬───┬───┐
│ 9 │ 8 │ 7 │ 6 │
└───┴───┴───┴───┘
  ▲           ▲
first       last