Stack: Minimum Element Lookup with O(1)

Problem Statement: 
    Implement a Stack with Minimum Element look-up in Constant time.


Solution:
Full Source Code : LINK

For this problem we would require extra stack which will maintain the Minimum element on the top. This stack will always have minimum element on the top.

We will be customizing the "Push" and "Pop" operations slightly of the Custom Stack in order for constant look-up of minimum element in the Stack.
We will be using two stacks viz.

1. Original Stack: Stack holding the elements
2. Min Stack : Stack holding min element on top

Fig: Original Stack and Min Stack for the given Sequence

1. Push Operation: 
           a) If element being pushed is smaller than the top element of Min Stack,
                           push to Original Stack and also Min Stack.
           b) If element being pushed is greater than the top element of Min Stack,
                           push to Original Stack.

Push Sub-routine implementation

1 2 3 4 5 6 7 8 9 10 11 12 13 14

/** * Push Subroutine */ @Override public void push(int data) { if(original.isEmpty()) minStack.push(data); else{ if(data < minStack.peek()) minStack.push(data); } original.push(data); }

2. Pop Operation:
          a) If top element of Original Stack is equal to top element of Min Stack
                         pop Original Stack and also pop Min Stack
          b) If top of Original Stack is not equal to top of Min Stack                    
                         pop Original Stack only.

Pop Sub-routine implementation

1 2 3 4 5 6 7 8 9 10

/** *Pops element from the custom stack */ @Override public int pop() { if(original.peek() == minStack.peek()) minStack.pop(); return original.pop(); }

 
3. Get Minimum Operation:
          Return the top element of Min Stack

4. Peek
        Return top element of Original Stack

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

/** * Peek Minimum Element */ @Override public int getMin(){ return minStack.peek(); } /** * Peek for the element */ @Override public int peek() { return original.peek(); } @Override public boolean isEmpty() { return original.isEmpty(); }

Please comment and post your suggestion. Please "Like" page on facebook if u liked the article.
Happy Coding!! :)