Problem: MinStack

Let’s look at a problem where we change the stack itself instead of using it to solve another problem.

Here is the interface for the MinStack ADT:

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

A MinStack is a Stack<Integer>: push, pop, top, and isEmpty behave exactly the way the Stack contract says. I fixed the element type to Integer so we can compare items easily. The one new method is getMin.

Here is a sequence of operations and what getMin must return after each one. The stack is written top first.

Operation	Stack (top first)	`getMin()`
`push(5)`	5	5
`push(2)`	2, 5	2
`push(2)`	2, 2, 5	2
`push(7)`	7, 2, 2, 5	2
`pop()`	2, 2, 5	2
`pop()`	2, 5	2
`pop()`	5	5
`pop()`	_	(throws `NoSuchElementException`)

Notice the duplicate 2s on the stack. Popping one of them leaves the minimum at 2. When the second 2 is popped, getMin has to return the earlier minimum, 5.

Every operation, including getMin, must run in $O (1)$ worst-case time. That means getMin cannot scan the stack.