Min Stack

July 27, 2012

Today’s exercise continues our occasional series of exercises based on interview questions:

Design a data structure that provides push and pop operations, like a stack, plus a third operation that finds the minimum element. All three operations must perform in constant time. You may assume that all elements are distinct.

Your task is to write the three indicated functions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

I think the push operation needs to add the new item to the minimum stack when it is less than or equal to the current minimum. Otherwise, a minimum item could get popped off to soon. Consider this sequence of operations:

push 5
push 3
push 3
pop <- returns 3, but also removes 3 from the top of the min stack
minimum <- should still return 3