Implementing Stack with GetMin operation

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 Min-stack 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 min-stack. If the new element is minimum, We have to push that element onto the min-stack too. We need not push that element on to min-stack if it is not lesser than top of min-stack.

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 Min-stack.

The following table explains the logic.



Operation
Stack
Min-stack
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 min-stack 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 min-stack because 3 is not minimum

  
Observe that top of min-stack 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 Min-stack is empty or
// newly inserted element is lesser, push it into min-stack 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 min-stack also
if( res == minStack.peek() )
{
minStack.pop();
}
return res;
}
//This function simply returns the top of min-stack
public int getMin()
{
return minStack.peek();
}
}
}