CSC236 Data Structures - Problem Set: Stacks

Problem Set: Stacks

Show what is written by the following segments of code.


a.   x = 3;
     y = 5;
     z = 2;
     ArrayBoundedStack<Integer> st = new ArrayBoundedStack<Integer>()
     st.push(x);
     st.push(4);
     z = st.top();
     st.pop();
     y = st.top();
     st.pop();
     st.push(y);
     st.push(3);
     st.push(2);
     x = st.top();
     st.pop();
     st.push(2);
     st.push(x);
     while (!st.isEmpty()) {
        x = st.top();
        st.pop();
        System.out.println(x);
     }


 b.  y = 1;
     ArrayBoundedStack<Integer> st = new ArrayBoundedStack<Integer>();
     st.push(5);
     st.push(7);
     x = st.top();
     st.pop();
     x = x + y;
     x = st.top();
     st.pop();
     st.push(x);
     st.push(y);
     st.push(2);
     y = st.top();
     st.pop();
     x = st.top();
     st.pop();
     while (!st.isEmpty()) {
        y = st.top();
        st.pop();
        System.out.println(y);
     }
     System.out.println("x = " + x);
     System.out.println("y = " + y);


c.   x = 0;
     y = 5;
     z = y / 2;
     st.push(x);
     st.push(y);
     z = st.top();
     st.pop();
     st.push(x+1);
     st.push(y);
     st.push(3);
     while (!st.isEmpty()) {
        z = st.top();
        st.pop();
        System.out.println(z);
     }
     System.out.println("x = " + x);
     System.out.println("y = " + y);
     System.out.println("z = " + z);


d.   a = 0;
     b = 5;
     c = 4;
     st.push(a);
     st.push(b);
     c = st.top();
     st.pop();
     a = a + 1;
     st.push(a);
     st.push(c);
     st.push(b);
     b = a + b;
     st.push(b);
     st.push(7);
     while (!st.isEmpty()) {
        a = st.top();
        st.pop();
        System.out.print(a + "  ");
     }

Suppose we use the array implementation for a stack st, which is a stack of Characters. Show what is on the stack st initially (draw the stack, showing what is on top), and then show the contents of topIndex, ch, and the array after each of the following operations. Indicate if there is an attempt to push to a full stack or pop from an empty stack. For each problem, start with the stack shown (not the result of the previous problem.)


   [0] [1] [2] [3] [4]
a.  B   C   D   F   O  	    topIndex = 1    ch = 'X'
                            ch = st.top();
                            st.pop();

    [0] [1] [2] [3] [4]
b.   X   Y   Z   A   B      topIndex = 4    ch = 'C'
                            st.push('A');

    [0] [1] [2] [3] [4]
c.   D   J   K   P   Q      topIndex = 3    ch = 'X'
                            st.push(ch);

    [0] [1] [2] [3] [4]
d.   R   V   M   H   A      topIndex = -1   ch = 'C'
                            ch = st.top();
                            st.pop();

Write a size method for the ArrayBoundedStack class that returns the number of items on the stack. Do not use any other methods of the stack class.
Write a size method for the LinkedStack class that returns the number of items on the stack. Do not use any other methods of the stack class.
Write a client function to copy one stack to another stack and leave the first stack unchanged. You may use an auxiliary stack if necessary.
Write a method public ArrayBoundedStack<T> copy() for the ArrayBoundedStack class which creates and returns a stack which is a copy of this. Do not use any other methods of the stack class.
Write a method public LinkedStack<T> copy() for the LinkedStack class which creates and returns a stack which is a copy of this. Do not use any other methods of the stack class.
Write a client function that will sum up all the negative values on a stack of Integers. Leave the stack unchanged and return the sum in a parameter. You may use an auxiliary stack if necessary.
Write a client function that will delete all the elements of a Character stack that contain the value 'A' while preserving the order of the other elements. You may use an auxiliary stack if necessary.
Write a method for the ArrayBoundedStack class called replace. This method returns void and takes as parms two vars of type T, called told and tnew. If the value told is found anywhere in the stack, replace it with the value tnew, while preserving the order of the values on the stack. If told is not found on the stack, do not change the stack. Do not use any other methods of the stack class.
Write a method for the LinkedStack class called replace. This method returns void and takes as parms two vars of type T, called told and tnew. If the value told is found anywhere in the stack, replace it with the value tnew, while preserving the order of the values on the stack. If told is not found on the stack, do not change the stack. Do not use any other methods of the stack class.
Write a method for the ArrayBoundedStack class called displayBack. This method returns void and has no parms. The function displays the values in the stack in reverse order; that is, display the top last. The output should appear on the screen. Do not use any other methods of the stack class.