Question

Define a class DoubleStack which implements two stacks of objects of type Object using a single shared array, so that the push and pop operations specify which of the two stacks is involved in the operation (as described below). (a) Specify necessary instance variables and write a constructor “DoubleStack(int n)” that takes integer n and creates an empty DoubleStack object with the shared array with room for n elements (2 pt); b) Write methods "boolean push(int i, Object o)" and "Object pop(int i)” which take the stack number i (0 or 1) as the first argument and perform the specified operation on the corresponding stack. Your "push” routine returns "true" if the object has been pushed and "false" if there is an overflow (no room to insert the object). You should not declare an overflow unless the whole array is completely full. Your "pop" returns "null" if the corresponding stack is empty. (6 pts -- 3 pts for each of the two methods).

Answer 1

Here is the completed code for this problem. Assuming the language is Java. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// DoubleStack.java

public class DoubleStack {

    private Object[] array;

    // defining two integer variables to denote top indices of each stack (next

    // available slots for new elements)

    private int stack1top;

    private int stack2top;

    // constructor

    public DoubleStack(int n) {

        // creating an Object array of n elements

        array = new Object[n];

        // initializing first index as stack1top and last index as stack2top

        stack1top = 0;

        stack2top = array.length - 1;

    }

    // method to push an element to first or second stack. if i=0, first stack,

    // if i=1, second stack

    public boolean push(int i, Object o) {

        // if stack1top exceeds stack2top, that is when the whole array is full

        if (stack1top > stack2top) {

             return false; // overflow

        }

        // checking if i is 0 or 1

        if (i == 0) {

             // adding to array at stack1top and incrementing stack1top

             array[stack1top] = o;

             stack1top++;

        } else if (i == 1) {

             // adding to array at stack2top and decrementing stack2top

             array[stack2top] = o;

             stack2top--;

        }

        return false; // invalid i

    }

    // removes and returns top element of a given stack

    Object pop(int i) {

        if (i == 0) {

             // if stack1top>0, it means that stack1 is not empty

             if (stack1top > 0) {

                 // decrementing stack1top

                 stack1top--;

                 // returning element at stack1top (previously stack1top-1)

                 return array[stack1top];

             }

        } else if (i == 1) {

             // if stack2top < array.length-1, it means that stack2 is not empty

             if (stack2top < array.length - 1) {

                 // incrementing stack2top

                 stack2top++;

                 // returning element at stack2top (previously stack2top+1)

                 return array[stack2top];

             }

        }

        return null; // stack is empty or i is invalid

    }

    // code for testing, remove if you dont want.

    public static void main(String[] args) {

        // creating a DoubleStack of size 50

        DoubleStack doubleStack = new DoubleStack(50);

        // adding numbers from 1 to 30 to stack1

        for (int i = 1; i <= 30; i++) {

             doubleStack.push(0, i);

        }

        // adding numbers from 1 to 25 to stack2, after 20 the doublestack will

        // be full, so elements from 21 to 25 will not be pushed to stack2

        for (int i = 1; i <= 25; i++) {

             doubleStack.push(1, i);

        }

        // displaying stack 1 element

        System.out.println("Stack 1:");

        // popping first element from first stack, if exists

        Object ob = doubleStack.pop(0); //note the index 0

        //looping until ob is null, printing ob, popping next element

        while (ob != null) {

             System.out.println(ob);

             ob = doubleStack.pop(0);

        }

        //doing the same for stack 2

        System.out.println("Stack 2:");

        ob = doubleStack.pop(1); //note the index 1

        while (ob != null) {

             System.out.println(ob);

             ob = doubleStack.pop(1);

        }

    }

}

/*OUTPUT*/

Stack 1:

30

29

28

27

26

25

24

23

22

21

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

Stack 2:

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1