Stack that Support Push, Pop, and GetMin in Constant Time

Source

Problem

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?

Solution

Use extra stack. Lets call it secondary stack.

push

-> if number is less then top of the stack element in secondary queue. Push it in secondary queue

-> push it in primary queue

pop

-> if top of the secondary queue == top of primary queue. Pop from secondary queue

-> pop from primary queue

-> pop from primary queue

get_minimum

-> return top of secondary queue