Pages

Saturday, August 5, 2017

Implement pop(), push(), min(), max() of Stack in O(1)

package algos;

public class SpecialStack {

int stack_size = 256;
int position;
int minPosition;;
int maxPosition;

int[] minStack;
int[] maxStack;
int[] stack;

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;

public boolean isEmpty(){
if(stack.length == 0){
return true;
}
return false;
}

public SpecialStack(){
stack = new int[stack_size];
minStack = new int[stack_size];
maxStack = new int[stack_size];
position = 0;
minPosition = 0;
maxPosition = 0;
}

public boolean isFull(){
if(stack.length == stack_size){
return true;
}
return false;
}

public int pop(){
position -= 1;
if(position < 0){
System.out.println("Stack is empty");;
}
if(stack[position] == minStack[minPosition-1]){
minPosition--;
}
if(stack[position] == maxStack[maxPosition-1]){
maxPosition--;
}
return stack[position];
}

public void push(int data){
if(position >= stack_size){
System.out.println("Stack Overflow");
}
stack[position] = data;
position++;
if(data < min){
minStack[minPosition] = data;
minPosition++;
min = data;
}
if(data > max){
maxStack[maxPosition] = data;
maxPosition++;
max = data;
}
}

public int min(){
return minStack[minPosition-1];
}

public int max(){
return maxStack[maxPosition-1];
}

public static void main(String[] args){
SpecialStack s = new SpecialStack();
s.push(10);
s.push(9);
s.push(100);
s.push(12);
s.push(13);
s.push(8);
s.push(7);
s.push(6);
s.push(5);
s.pop();
s.pop();
s.push(1);
s.push(-1);
s.push(5);
s.push(15);
s.push(20);

System.out.println(s.min());
System.out.println(s.max());


}
}

No comments:

Post a Comment