Solution: Copying MinStack

Suppose we did not have to use deques to build MaxQueue. Could we build one with the trick we used for MinStack?

Recall that in LinkedMinStack, every node carries a minPointer to the node holding the smallest value at or below it. push sets the pointer on the new node by comparing the new item with the current minimum. getMin follows one pointer from the top. pop needs no extra work at all.

Let’s copy it onto the LinkedQueue from the queue chapter. Every node gets a maxPointer to the node holding the largest value among itself and the nodes in front of it, the ones that were already in the queue when it arrived.

private static class Node {
  int value;
  Node maxPointer;  // the node holding the largest value at or in front of this one
  Node next;

  Node(int value) {
    this.value = value;
  }
}

enqueue sets the pointer on the new node the way push does in MinStack: if the new item is larger than the current maximum, the new node points at itself; otherwise it copies the pointer from the node before it, which is tail.

public void enqueue(int item) {
  Node newNode = new Node(item);
  if (isEmpty() || item > tail.maxPointer.value) {
    newNode.maxPointer = newNode;  // the new item is the new maximum
  } else {
    newNode.maxPointer = tail.maxPointer;
  }
  // link newNode after tail and move tail, as in LinkedQueue
}

The tail node arrived last, so its pointer covers every node in the queue. getMax follows one pointer from the tail:

public int getMax() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return tail.maxPointer.value;
}

dequeue is unchanged from LinkedQueue: it moves head to the next node. Every operation is $O(1)$. Now we have to check whether it gives the right answer.

Enqueue 7, 2, 5, 1, 4. The m→ annotation under each node shows the value held by the node its maxPointer points to. The 7 points at itself, and every later node copies that pointer, because none of them is larger than 7:

          ┌───┐      ┌───┐      ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 7 │ ──▶  │ 2 │ ──▶  │ 5 │ ──▶  │ 1 │ ──▶  │ 4 │ ──▶ null
          └───┘      └───┘      └───┘      └───┘      └───┘
            ▲          ▲          ▲          ▲          ▲
           m→7        m→7        m→7        m→7        m→7
                                                      tail

getMax() follows the tail’s pointer and returns 7, which is correct.

Now dequeue(). The head moves to the node holding 2, and the node holding 7 is gone:

          ┌───┐      ┌───┐      ┌───┐      ┌───┐
head ───▶ │ 2 │ ──▶  │ 5 │ ──▶  │ 1 │ ──▶  │ 4 │ ──▶ null
          └───┘      └───┘      └───┘      └───┘
            ▲          ▲          ▲          ▲
           m→7        m→7        m→7        m→7
                                           tail

Every remaining pointer still points at the node holding 7. That node is no longer in the queue. getMax() returns 7 when the answer is 5.

In the MinStack problem we asked whether a minPointer can ever point to a popped node, and the answer was no: it points to a node at or below its own, and a stack removes only from the top. The queue does not have that property. A maxPointer points to a node at or in front of its own, and a queue removes from the front. So the node it points to is exactly the kind of node that gets removed. The first time the maximum is dequeued, every pointer that was set while it was in the queue goes stale at once.

Could we point the other way, with each node pointing to the largest node at or behind it? Then dequeue would be safe, since removing the front node cannot break a pointer that points behind. But a new node arrives behind every node in the queue, so it can change the pointer of every one of them. Enqueue 1, 2, 3, then 9, and all three earlier nodes have to be repointed at 9. That makes enqueue $O(n)$.

So a single pointer per node does not carry over from the stack to the queue.