In this post we discuss how to efficiently implement a stack data structure with one additional operation getMin() along with push() and pop(). getMin() returns the minimum value in the stack.
The trick here is to use another stack which stores the minimum values of the original stack. The top of Minstack always contains the minimum of stack elements so far inserted.
The Push operation is implemented as follows.
When an element is pushed on to the stack, we have to compare that with top of minstack. If the new element is minimum, We have to push that element onto the minstack too. We need not push that element on to minstack if it is not lesser than top of minstack.
The Pop operation is implemented as follows.
While popping the element from the original stack, we should also make sure that if minimum element is popped, it should also be removed from Minstack.
The following table explains the logic.
Observe that top of minstack always contains the minimum element.
Following is the Java code which implements the above approach.
The trick here is to use another stack which stores the minimum values of the original stack. The top of Minstack always contains the minimum of stack elements so far inserted.
The Push operation is implemented as follows.
When an element is pushed on to the stack, we have to compare that with top of minstack. If the new element is minimum, We have to push that element onto the minstack too. We need not push that element on to minstack if it is not lesser than top of minstack.
The Pop operation is implemented as follows.
While popping the element from the original stack, we should also make sure that if minimum element is popped, it should also be removed from Minstack.
The following table explains the logic.
Operation

Stack

Minstack

Description

Push(5)

5

5

5 pushed on to both the stacks

Push(2)

5 2

5 2

2 is pushed to both stacks

Push(3)

5 2 3

5 2

3 is not pushed to minstack because it is not minimum

Push(1)

5 2 3 1

5 2 1

1 is pushed to both because it is new minimum

Pop()

5 2 3

5 2

1 is popped from both because it is minimum

Pop()

5 2

5 2

No need to pop from minstack because 3 is not minimum

Observe that top of minstack always contains the minimum element.
Following is the Java code which implements the above approach.
import java.util.Stack; /** * Created with IntelliJ IDEA. * User: Ravi * Date: 9/4/13 * Time: 7:04 AM * To change this template use File  Settings  File Templates. */ public class Main { public static void main(String[] args) { MinStack mStack = new MinStack(); mStack.push(5); System.out.println(mStack.getMin()); mStack.push(2); System.out.println(mStack.getMin()); mStack.push(3); System.out.println(mStack.getMin()); mStack.push(1); System.out.println(mStack.getMin()); mStack.pop(); System.out.println(mStack.getMin()); mStack.pop(); mStack.pop(); System.out.println(mStack.getMin()); } static class MinStack { Stack<Integer> dataStack; Stack<Integer> minStack; public MinStack() { dataStack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public void push(int d) { //Push that element to the original stack dataStack.push(d); //If either Minstack is empty or // newly inserted element is lesser, push it into minstack also if( minStack.empty()  d < minStack.peek()) { minStack.push(d); } } public int pop() { //pop the element from the original stack int res = dataStack.pop(); //If the popped element is also the minimum, //pop from the minstack also if( res == minStack.peek() ) { minStack.pop(); } return res; } //This function simply returns the top of minstack public int getMin() { return minStack.peek(); } } }