Stack Implemetation with Push, Pop, GetMin and GetMax in constant time - Java

public class Stack {
    int TOP = -1;
    static final int MAX = 10;
    int[] stack = new int[MAX];

    public boolean isEmpty(){
        if(TOP == -1)
            return true;
        else
            return false;
    }

    public boolean isFull(){
        if(TOP == MAX)
            return true;
        else
            return false;
    }

    public int pop() {
        int popEle = 0;
        if (!isEmpty()) {
            popEle = stack[TOP];
            TOP--;
        }
        return popEle;
    }

    public void push(int ele){
        if(!isFull()){
            TOP = TOP + 1;
            stack[TOP] = ele;
        }
    }
}


public class SpecialStack extends Stack {
    Stack minStack = new Stack();
    Stack maxStack = new Stack();

    public void push(int ele){
        if(isEmpty()){
            super.push(ele);
            minStack.push(ele);
            maxStack.push(ele);
        }else{
            if(minStack.stack[TOP] > ele){
                super.push(ele);
                minStack.push(ele);
                maxStack.push(maxStack.stack[TOP - 1]);
            }else if(maxStack.stack[TOP] < ele){
                super.push(ele);
                maxStack.push(ele);
                minStack.push(minStack.stack[TOP - 1]);
            }
        }
    }

    public int pop(){
        minStack.pop();
        maxStack.pop();
        return super.pop();
    }

    public int getMin(){
        int min = minStack.pop();
        minStack.push(min);
        return min;
    }

    public int getMax(){
        int max = maxStack.pop();
        maxStack.push(max);
        return max;
    }

    public static void main(String[] args) {
        SpecialStack s = new SpecialStack();
        s.push(10);
        s.push(2);
        s.push(20);
        s.push(30);
        s.push(15);
        System.out.println("Max "+s.getMax());
        System.out.println("Min "+s.getMin());
        s.push(5);
        s.push(50);
        System.out.println("Max "+s.getMax());
        System.out.println("Min "+s.getMin());
    }
}

o/p:
Max 30
Min 2
Max 50
Min 2

Comments

Popular posts from this blog

EJB - Stateful vs Stateless

Mirror binay tree - Java