Two stacks in a single array-- simulation

Hi All,

The topic of discussion for today is implementing two stacks in a single array.

package algorithms;

public class TwoStacksInASingleArray {

    int stack[];
   
    /* for two stacks*/
    int top1,top2;
   
    /* logic two stacks grow in opposite directions. One upwards one downwards*/
   
    public TwoStacksInASingleArray(int size){
        stack=new int[size];
       
        top1=-1;
       
        top2=size;
    }
   
   
   
    public static void  main(String args[]){
       
        TwoStacksInASingleArray tst=new TwoStacksInASingleArray(10);
       
        tst.push1(1);
        tst.push2(2);
        tst.push1(3);
        tst.push2(4);
        tst.push1(5);
        tst.push1(6);
        tst.push1(7);
        tst.push1(8);
        tst.push1(9);
        tst.push2(10);
        tst.display();
       
        tst.pop1();
        tst.pop2();
        tst.pop1();
        tst.pop1();
        tst.pop1();
        tst.pop1();
        tst.pop2();
        tst.pop2();
        tst.pop2();
        tst.pop2();
        tst.pop1();
        tst.pop1();
        tst.pop1();
       
        //tst.display();
       
        tst.push1(9);
        tst.push2(10);
        tst.display();
       
    }
   
   
    public void push1(int value){
       
        /* check if stack is already full*/
       
        if(isStack1Full()){
            System.out.println("\n stack1 is full");
        }
        else{
            top1++;
           
            stack[top1]=value;
        }
       
       
    }
   
   
public void push2(int value){
       
        /* check if stack is already full*/
       
        if(isStack2Full()){
            System.out.println("\n stack2 is full");
        }
        else{
            top2--;
           
            stack[top2]=value;
        }
       
       
    }

public int pop1(){
   
    /* check for underflow*/
   
    if(isStack1Underflow()){
        System.out.println("\nStack1 Underflow");
        return -1;
    }
    else{
        int ret=stack[top1];
        System.out.println("\n Popped element is "+ret);
       
        stack[top1--]=0;
        return ret;
    }
}


public int pop2(){
   
    /* check for underflow*/
   
    if(isStack2Underflow()){
        System.out.println("\nStack2 Underflow");
        return -1;
    }
    else{
        int ret=stack[top2];
        System.out.println("\n Popped element is "+ret);
       
        stack[top2++]=0;
        return ret;
    }
}
   
    boolean isStack1Full(){
        if(top1==stack.length-1){
            return true;
        }
        else if(top1+1==top2){
            return true;
        }
        else{
            return false;
        }
    }
   
   
    boolean isStack2Full(){
        if(top2==0){
            return true;
        }
        else if(top2-1==top1){
            return true;
        }
        else{
            return false;
        }
    }
   
   
    public boolean isStack1Underflow(){
       
        if(top1==-1){
            return true;
        }
        else{
            return false;
        }
    }
   
public boolean isStack2Underflow(){
       
        if(top2==stack.length){
            return true;
        }
        else{
            return false;
        }
    }
   
    public void display(){
       
        for(int i:stack){
            System.out.println(i+"\n");
        }
    }
   
}

From the above code it is evident that one stack with top1 is growing upwards, while the other with top2 is growing downwards. Rest is similar to the usual single stack using an array except the conditions for underflow and overflow will be little changed as shown to include for the other stack.

As is the case always you can still improve the above algorithm as an exercise . If you do so kindly post it here. It could be helpful to someone.

Thanks in advance .

Cheers .

Subbu.