public class MinStackArray {
private class Node{
private int value;
private int minValue;
}
Node[] array;
int N;
public MinStackArray(int capacity){
array = new Node[capacity];
N = 0;
}
public void push(int value){
if(N >= array.length )
resize();
Node newNode = new Node();
newNode.value = value;
if(N == 0){
newNode.minValue = value;
}else{
Node headNode = array[N-1];
if(headNode.minValue < value)
newNode.minValue = headNode.minValue;
else
newNode.minValue = value;
}
array[N++] = newNode;
}
public int pop(){
if(N == 0)
return -1;
Node head = array[--N];
return head.value;
}
public int getMin(){
if(N == 0)
return -1;
Node head = array[N-1];
return head.minValue;
}
private void resize(){
Node[] newArray = new Node[array.length*2];
int counter =0;
for(Node c :array){
newArray[counter++] =c;
}
array = newArray;
}
public static void main(String[] argv){
MinStackArray msa = new MinStackArray(2);
msa.push(5);
msa.push(7);
msa.push(3);
msa.push(9);
msa.push(1);
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
msa.pop();
System.out.println(msa.getMin());
}
}
Saturday, February 8, 2014
MinStack
I was asked a question about how would i implement a Stack without using Linked List structure that supports push, pop and getMin operation, so this is the solution.
Basic idea is you maintain Node object which has value of the node and the minimum value at that point. Every time push() is called you have to see if the value being pushed is smaller than current minimum if yes it becomes new minimum and you push it on stack with current value, if not you take current minimum and push it on stack with value being pushed. Problem with this solution is it will take twice the memory
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment