Max stack: a stack that can pop its largest value

Design a stack that, besides the usual operations, can return the largest value and remove it. When the largest value appears more than once, pop_max removes the copy closest to the top.

Interface

Unless you agree on a different interface with the interviewer, assume:

• push(x: int) -> None
• pop() -> int — removes and returns the top value.
• top() -> int — returns the top value without removing it.
• peek_max() -> int — returns the largest value in the stack.
• pop_max() -> int — removes and returns the largest value, the copy nearest the top on ties.
• pop, top, peek_max and pop_max are never called on an empty stack.

Example

push(5); push(1); push(5)
top()       ->  5
pop_max()   ->  5     # removes the upper 5; the stack is [5, 1]
top()       ->  1
peek_max()  ->  5
pop()       ->  1
top()       ->  5

Constraints

• Up to 2 * 10^4 operations; values in [-10^9, 10^9].

Clarifying questions

• On ties, which copy does pop_max remove?
• Will operations ever be called on an empty stack, and what should they do?
• Which operations matter most for speed? Is O(n) pop_max acceptable?

What a strong answer covers

• The two-stack design: a main stack and a stack of running maxima. push, pop, top and peek_max are O(1); pop_max pops into a buffer until it reaches the maximum, removes it and pushes the buffer back, O(n).
• The O(log n) design: a doubly linked list for stack order plus a sorted map from value to a list of its nodes (or a max-heap with lazy deletion keyed by value and insertion order); pop_max unlinks the most recent node of the largest value.
• The cost of each operation in both designs, and when the simpler one is the right choice.
• Tests: duplicate maxima, pop_max when the max is at the top, alternating pop and pop_max.

Follow-ups

• Add pop_min as well.
• Make every operation O(1) amortised except pop_max, and prove it.
• Make the stack safe to use from several threads.