Finding the Minimum element of a stack in O(1) time

Write the algo to return the Minimum element of a stack in O(1) time.

Answer:


Along with the normal stack, use another stack called the min stack.
The top of the min stack is ensured to have the min element as follows.
The elements are added to the min stack as follows:
During Push:
1. If the min stack is empty, then push the element that is being pushed into regular stack.
2. If the min stack is not empty, then if the element being pushed is <= MinStack.Top(), then push the element to MinStack.
During Pop:
3. If the element being popped from the normal stack is < element on min stack, then pop the element from min stack as well, or else leave the min stack untouched.

Ex: 6  8  2 3 7 1 9

After Push:

Regular stack:
6 8 2 3 7 1 9
Min Stack:
6 2 1

After Poping 9:
Regular stack:
6 8 2 3 7 1
Min Stack:
6 2 1

After Poping 1:
Regular stack:
6 8 2 3 7
Min Stack:
6 2

After Poping 3 , 7:
Regular stack:
6 8 2
Min Stack:
6 2

After Poping 2:
Regular stack:
6 8
Min Stack:
6

:
:
:
:
so on