How To Design a stack which returns minimum element in constant time?

Design a stack to support an additional operation which returns the minimum element from the stack in constant time. The stack should continue supporting all other operations like push, pop, top, size, empty, etc, with no degrade in performance for these operations.

 
The first solution that appears in mind is to have a member variable in a stack to keep track of the minimum number. Unfortunately, this won’t work as we can’t get the next minimum number after the minimum one is popped.
 
The correct approach is to use two stacks – the main stack to store the actual stack elements and an auxiliary stack to store the required elements needed to determine the minimum number in constant time. This implementation requires few changes in push and pop operations:

1. Push operation
The idea is to push the new element into the main stack and push it into the auxiliary stack only if stack is empty or the new element is less than or equal to the current top element of the auxiliary stack.

2. Pop operation
For pop operation, we remove the top element from the main stack and remove it from the auxiliary stack only if it is equal to the current minimum element. i.e. top element of both main stack and auxiliary stack are same. After the minimum number is popped, the next minimum number appears on the top of auxiliary stack.

3. Min operation
The top of the auxiliary stack always returns the minimum number since we are pushing the minimum number into the auxiliary stack and removing the minimum number from the auxiliary stack only if it is removed from the main stack.
 
Below table demonstrates the above operations:
 
Stack Operations
 
This is illustrated below in C++/Java: