Stack DS to implement constant time Minimum element lookup

Problem: You need to implement a stack data structure that can also report the minimum element in constant-time.

Solution

Method 1 - Using extra stack
This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. So we need to keep some auxiliary list of the stack items so we can update the minimum variable after we pop items.

A clever way to do that is to use another stack that stores the minimum of all items in the stack. The minimum value is calculated when items are pushed to the stack and when items are popped from the stack we also pop from the minStack to reveal the new minimum value.

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.

You can refer to this question (Question 2) here - http://k2code.blogspot.in/2011/12/some-stack-question.html

class MinStack  <T extends Comparable<T>>  
{  
   private Stack<T> minStack = new Stack<T>();  
   private Stack<T> stack = new Stack<T>();  
  
 public T getMinimum()  
    {  
        return minStack.peek();   
    }  
  
    public void Push(T element)  
    {  
        stack.push(element);  
        if (minStack.size() == 0 || element.compareTo(minStack.peek()) <= 0)  
        {  
            minStack.push(element);  
        }  
        else  
            minStack.push(minStack.peek());  
    }  
  
    public T Pop()  
    {  
        minStack.pop();  
        return stack.pop();  
    }  
}  

Thanks