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.

Stacks-- parenthesis matching

Hi All,

Today our topic of discussion is checking the correctness of parenthesis I mean matching right and left parenthesis using stack.

static Stack<Character> s=new Stack<Character>();

   

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

       

       

        boolean hasMoreChars=true;

       

        char nextChar='A';

        DataInputStream din=new DataInputStream(System.in);

        while(hasMoreChars){

            try{

                System.out.println("\n Enter a character");

            nextChar=(din.readLine()).charAt(0);

           

            System.out.println(nextChar);

            }

            catch (Exception e) {

                // TODO: handle exception

                e.printStackTrace();

                System.exit(0);

            }

           

            if(nextChar==-1){

                System.out.println("in If\n");

                hasMoreChars=false;

            }

           

            else{

                System.out.println("\n In else");

            if(nextChar=='('||nextChar=='{'||nextChar=='['){

               

                System.out.println("\n In push");

                s.push(nextChar);

            }

            else if(nextChar==')'||nextChar=='}'||nextChar==']'){

               

                System.out.println("\n In pop");

                if(s.isEmpty()){

                    System.out.println("\n there is a mismatch");

                }

               

                else{

                if(nextChar==')'){

                    if(s.pop()=='('){

                        continue;

                       

                    }

                    else{

                        System.out.println("\n there is a mismatch");

                    }

                }

               

                if(nextChar=='}'){

                    if(s.pop()=='{'){

                        continue;

                       

                    }

                    else{

                        System.out.println("\n there is a mismatch");

                    }

                }

               

                if(nextChar==']'){

                    if(s.pop()=='['){

                        continue;

                       

                    }

                    else{

                        System.out.println("\n there is a mismatch");

                    }

                }

               

            }

           

           

        }

    }

   

   

   

}

    }

for the purpose focusing on the problem at hand , not on stack, I have used the stack class in util.  Further more there are some minor mistakes in the above code. It is left for your to find out the mistakes and rectify them as an execercise.

Arrays using stacks.

Hi all,

The following code is for implementing array structure using stacks.The implementation is not complete (it doesnt include runtime exception checkings etc) to focus more on logic rather than validations.

package algorithmProblems;

import java.util.Stack;

public class ArrayUsingStack {
   
   
    public static void main(String args[]){
    Array2 ar=new Array2(10);
   
    ar.disp();                       
    ar.set(11, 5);
    ar.disp();
   
    System.out.println(ar.get(4));
    }
}

class Array2{
   
    Stack s1,s2;
    Array2(int size){
        s1=new Stack();
        s2=new Stack();
        s1.setSize(size);
        s2.setSize(size);
        System.out.println(s1.size());
        for(int i=0;i<s1.size();i++){
            s1.set(i,i);/* instead you can create a method initialize and call it in constructor.. actually we shouldnt use this set method . I have used for clarity */
           
        }
}
   
    public void add(int value){
        s1.push(value);
    }
   
    public Object get(int index){
        int diff=s1.size()-index;
        int ret=0;
       
       
        for(int i=0;i<diff;i++){
           
            s2.push(s1.pop());
           
           
        }
        ret=(Integer)s1.peek();
        for(int i=0;i<diff;i++){
            s1.push(s2.pop());
        }
        return ret;
    }
   
    public void disp(){
        System.out.println(s1);
    }
   
    public void set(int index,int value){
       
        if(index>s1.size()){
            System.out.println("Array Index out of Bounds");
            return;
        }
        int diff=s1.size()-index;
        System.out.println(s1);
        for(int i=0;i<diff+1;i++){
            s2.push(s1.pop());
        }
        s1.push(value);
        for(int i=0;i<diff;i++){
            s1.push(s2.pop());
        }
       
       
       
    }
   
}

From the above program the logic is clear we need to copy some elements to another stack and perform the operation and then again push the elements back to original stack. You can add further operations/validations as an excercise.