Push(),Pop(), and GetMin() elements at complexity O(1)

Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

http://www.geeksforgeeks.org/design-and-implement-special-stack-data-structure/
http://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/

Method 1:2 stacks
A constant time minimum lookup can be achieved by using an extra stack. Let's call this stack 'min_stack'. This stack will always have the minimum value at the top.

Modify 'push' and 'pop' operations as follows:

push:
- If the element being pushed is less than the top element of 'min_stack' then push it on 'min_stack' as well.
- Else, push the top element of 'min_stack' again on 'min_stack'.

pop:
- Every time you pop an element from the original stack, pop from 'min_stack' as well.

Example:
Suppose, elements are pushed in the following order: 7 3 5 8 9 1 2

original_stack                min_stack
        2                                 1
        1                                 1
        9                                 3
        8                                 3
        5                                 3
        3                                 3
        7                                 7

You can see that at any stage, the 'min_stack' can be queried for the minimum element in the stack.

Method 2:Single Stack

PUSH : While inserting the element into stack we insert the element and also keep track of minimum element at every insert and also insert the minimum element. This doubles up the stack usage to 2n. where n is number of element. O(1).

POP : While extracting element out of the stack, we need to extract two elements one is the minimum element tracked so far and the actual element of the array. O(1)

FIND MIN:Single pop operation will be able to fetch the minimum element. O(1).