Problem: MaxQueue

We have done two things with ADTs in the practice problems so far. In the stack chapter, the MinStack problem changed the stack itself: it kept the Stack contract and added one operation, getMin. In the queue chapter, the Queue with Two Stacks problem built a queue out of two stacks. This problem does both. We change the queue by adding a getMax operation, and we build the new queue out of deques.

Here is the skeleton of the class:

public class MaxQueue {
  public void enqueue(int item) {
    // ...
  }

  public void dequeue() {
    // ...
  }

  public int front() {
    // ...
  }

  public int getMax() {
    // ...
  }

  public boolean isEmpty() {
    // ...
  }
}

The first four operations follow the Queue contract from the queue chapter: enqueue adds at the back, dequeue removes the front item without returning it, front reports the front item, and isEmpty reports whether the queue is empty. The new operation is getMax. I fixed the element type to int so we can compare items easily.

Here is a sequence of operations and what getMax must return after each one. The queue is written front first.

Look at the first dequeue(). When 7 leaves, four items remain in the queue, and getMax has to report the largest of them, 5, without scanning them. Two rows later, 5 leaves and getMax has to report 4.

The problem has a constraint: enqueue, dequeue, front, getMax, and isEmpty must all run in amortized $O(1)$ time. A single call may cost more than $O(1)$, so part of this problem is to work out what the operations cost over a sequence of calls, the way we did for the queue with two stacks.

Let’s think of some special or edge cases as well:

• front, dequeue, and getMax on an empty MaxQueue should throw a NoSuchElementException.
• Duplicates count separately. If the queue holds 5, 5, 2, then getMax is 5. After one dequeue, getMax is still 5.