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();
}
}
}