Challenge: Constant-Time Min-Element Stack

Here’s another problem from the Algorithm Design Manual (Skiena), Interview Problem 4-44:

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?
Hint 1
Constant time? Well then it’s stacks all the way down.
Hint 2
Two stacks, to be exact.
Data structure contains two stacks, all and mins. is the minimum element. After calling all.push(), push to mins if <= Before calling all.pop(), pop from mins if ==

Leave a Reply

Your email address will not be published. Required fields are marked *