Solution: Two MaxStacks

There is a second way to build MaxQueue, and it uses the two earlier problems directly. In the Queue with Two Stacks problem we built a queue out of two stacks. In the MinStack problem we gave a stack a getMin operation. Put those together: build the queue out of two stacks, and make each stack one that reports its maximum. This solution sets aside the problem’s rule that deques are the only storage, to show a second design built from those two problems.

First the stack. A MaxStack is MinStack with the comparison turned around. The interface adds getMax to Stack<Integer>:

public interface MaxStack extends Stack<Integer> {
  /**
   * Returns the largest item on this stack without removing it.
   * @return the largest item on this stack
   * @throws NoSuchElementException if this stack is empty
   */
  Integer getMax();
}

LinkedMaxStack is LinkedMinStack with a maxPointer in place of the minPointer. Only push and getMax differ from LinkedStack:

@Override
public void push(Integer item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  Node newNode = new Node(item);
  if (isEmpty() || item > head.maxPointer.value) {
    newNode.maxPointer = newNode;  // the new item is the new maximum
  } else {
    newNode.maxPointer = head.maxPointer;
  }
  newNode.next = head;
  head = newNode;
}

@Override
public Integer getMax() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return head.maxPointer.value;
}

Every operation of LinkedMaxStack is $O (1)$ worst case, by the same argument as for LinkedMinStack.

Now the queue. We take StackQueue from the Queue with Two Stacks problem and change the type of its two stacks. The queue’s largest item is on one of the two stacks, so getMax asks both and returns the larger answer, skipping a stack that is empty.

public class MaxQueue {
  private MaxStack in = new LinkedMaxStack();   // receives enqueued items
  private MaxStack out = new LinkedMaxStack();  // serves items, oldest on top

  public void enqueue(int item) {
    in.push(item);
  }

  public void dequeue() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    pour();
    out.pop();
  }

  public int front() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    pour();
    return out.top();
  }

  public int getMax() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }
    if (in.isEmpty()) {
      return out.getMax();
    }
    if (out.isEmpty()) {
      return in.getMax();
    }
    return Math.max(in.getMax(), out.getMax());
  }

  public boolean isEmpty() {
    return in.isEmpty() && out.isEmpty();
  }

  // if out is empty, move everything from in to out, reversing the order
  private void pour() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) {
        int item = in.top();
        in.pop();
        out.push(item);
      }
    }
  }
}

Each item poured into out is pushed onto a MaxStack, so its maxPointer is set when it is pushed, and out.getMax() is correct for whatever out holds. The same goes for in. So getMax is correct as long as the two stacks together hold the queue, and they always do.

Let’s trace the sequence from the problem statement: enqueue(7), enqueue(2), enqueue(5), enqueue(1), enqueue(4), and then three calls to dequeue(). The m→ annotation next to each item shows the value its maxPointer points to.

The five enqueues push onto in. The 7 is at the bottom and its maxPointer points at its own node. Every later item is smaller than 7, so it copies the maxPointer of the node below it:

     in               out
┌───┐               (empty)
│ 4 │ m→7  ◀── top
├───┤
│ 1 │ m→7
├───┤
│ 5 │ m→7
├───┤
│ 2 │ m→7
├───┤
│ 7 │ m→7
└───┘

getMax() finds out empty and returns in.getMax(), which is 7.

The first dequeue() finds out empty and pours. The items are pushed onto out in the order 4, 1, 5, 2, 7, and each one sets its maxPointer as it is pushed: 4 points at itself, 1 copies 4, 5 points at itself, 2 copies 5, 7 points at itself. Then the dequeue pops 7:

     in               out
(empty)          ┌───┐
                 │ 2 │ m→5  ◀── top
                 ├───┤
                 │ 5 │ m→5
                 ├───┤
                 │ 1 │ m→4
                 ├───┤
                 │ 4 │ m→4
                 └───┘

getMax() finds in empty and returns out.getMax(). The top of out is 2, and its maxPointer points at 5. That is the right answer: the queue holds 2, 5, 1, 4, and we did not scan those four items to get it. The maxPointer of each node below 7 was set before 7 was pushed, and popping 7 did not change them, because a stack removes only from the top.

The second dequeue() pops 2. The new top is 5, pointing at itself, so getMax() returns 5. The third dequeue() pops 5. The new top is 1, pointing at 4, so getMax() returns 4:

     in               out
(empty)          ┌───┐
                 │ 1 │ m→4  ◀── top
                 ├───┤
                 │ 4 │ m→4
                 └───┘

front, dequeue, and getMax check isEmpty first and throw NoSuchElementException when the queue is empty. Duplicates work because push uses a strict comparison: a second 5 pushed onto a stack whose maximum is 5 copies the maxPointer, which points at the first 5, and popping either of them leaves the other as the maximum.

What does this cost? enqueue is one push. getMax is at most two getMax calls on the stacks and one comparison. isEmpty is two checks. All $O (1)$ . dequeue and front are amortized $O (1)$ by the pour argument from the Queue with Two Stacks problem: each item is pushed onto in once, poured at most once, and popped from out at most once, so it is responsible for at most four stack operations from enqueue to dequeue. The maxPointer adds a constant amount of work to each push and no work to a pop.

The space is $O (n)$ for a queue of $n$ items, and it is always $O (n)$ : every node carries one extra reference, whether or not that node could ever be the maximum.

Let’s compare the two solutions:

Time. Both give amortized $O (1)$ on every operation. In the two-deques solution the expensive operation is enqueue, when it removes many candidates. In the two-MaxStacks solution the expensive operations are dequeue and front, when they pour. Neither has a worst-case $O (1)$ bound on every operation.
Space. The two-MaxStacks solution stores every item plus one reference per item. The two-deques solution stores every item once in items and the candidates again in candidates. In the worst case, a decreasing sequence, every item is a candidate and the two solutions use the same space. In the common case the candidate deque is much smaller than the queue.