CS210 Tutorials with Dr. Basit Qureshi

CS210 Tutorial 7

Complete the following exercises pasted below:

Q1. Suppose an initially empty stack S has performed a total of 25 push operations, 12 top operations, and 10 pop operations, 3 of which returned null to indicate an empty stack. What is the current size of S?

Given:

Push operations: 25
Pop operations: 10
Null pops (empty stack): 3
Top operations: 12 (do not affect size)

Step 1: Calculate Successful Pops

Successful pops = Total pops − Null pops = 10 − 3 = 7

Step 2: Calculate Current Stack Size

Current size = Pushes − Successful pops = 25 − 7 = 18

Final Answer

The current size of stack S is 18.

Q2. What values are returned during the following series of stack operations, if executed upon an initially empty stack?

push(5), push(3), pop(), push(2), push(8),

pop(), pop(), push(9), push(1), pop(), 

push(7), push(6), pop(), pop(), push(4),

pop(), pop().

Operation	Stack (Bottom → Top)	Returned Value
push(5)	5	-
push(3)	5, 3	-
pop()	5	3
push(2)	5, 2	-
push(8)	5, 2, 8	-
pop()	5, 2	8
pop()	5	2
push(9)	5, 9	-
push(1)	5, 9, 1	-
pop()	5, 9	1
push(7)	5, 9, 7	-
push(6)	5, 9, 7, 6	-
pop()	5, 9, 7	6
pop()	5, 9	7
push(4)	5, 9, 4	-
pop()	5, 9	4
pop()	5	9

Returned Values (in Order)

3, 8, 2, 1, 6, 7, 4, 9

Final Stack

Remaining stack: 5

Q3. Implement a method with signature duplicate(Stack S) that creates a new stack and copies all elements from S to the new stack. It then returns the copied stack.

    public static Stack duplicate(Stack S) {

        Stack temp = new Stack();
        Stack T = new Stack();

        // Step 1: Move S to temp
        while (!S.isEmpty()) {
            temp.push(S.pop());
        }

        // Step 2: Move temp to T
        while (!temp.isEmpty()) {
            int X = temp.pop();
            T.push(X);
            S.push(X);
        }
        return T;
    }

Q4. Suppose you have a non-empty stack S of type integers. Write a method that searches and removes value X in the stack S. Make sure the order of items in the stack are unchanged. If X is not found the method returns false, otherwise true.

    public static boolean searchAndRemove(Stack S, int X) {
        if (S == null || S.isEmpty()) {
            return false;
        }

        boolean found = false;
        Stack T = new Stack();

        // Step 1: Search for X and move elements to tempStack
        while (!S.isEmpty()) {
            int current = S.pop();
            if (current == X && !found) {
                found = true; // Found X, skip pushing to tempStack (remove it)
            } else {
                T.push(current);
            }
        }

        // Step 2: Restore original order (excluding the removed X)
        while (!T.isEmpty()) {
            S.push(T.pop());
        }

        return found;
    }

Q5. What values are returned during the following sequence of queue operations, if executed on an initially empty queue?

enqueue(5), enqueue(3), dequeue(),

enqueue(2), enqueue(8), dequeue(), dequeue(), enqueue(9), enqueue(1),

dequeue(), enqueue(7), enqueue(6), dequeue(), dequeue(), enqueue(4),

dequeue(), dequeue().

Given Operations:

enqueue(5), enqueue(3), dequeue(),
enqueue(2), enqueue(8), dequeue(), dequeue(), enqueue(9), enqueue(1),
dequeue(), enqueue(7), enqueue(6), dequeue(), dequeue(), enqueue(4),
dequeue(), dequeue().

Step-by-Step Execution

Operation	Queue (Front → Rear)	Returned Value
enqueue(5)	5	-
enqueue(3)	5, 3	-
dequeue()	3	5
enqueue(2)	3, 2	-
enqueue(8)	3, 2, 8	-
dequeue()	2, 8	3
dequeue()	8	2
enqueue(9)	8, 9	-
enqueue(1)	8, 9, 1	-
dequeue()	9, 1	8
enqueue(7)	9, 1, 7	-
enqueue(6)	9, 1, 7, 6	-
dequeue()	1, 7, 6	9
dequeue()	7, 6	1
enqueue(4)	7, 6, 4	-
dequeue()	6, 4	7
dequeue()	4	6

Returned Values (in Order)

5, 3, 2, 8, 9, 1, 7, 6

Final Queue State

Remaining queue: 4

Q6. Suppose you have a queue D containing the numbers (1,2,3,4,5,6,7,8), in this order. Suppose further that you have an initially empty Stack S. Give a code fragment that uses S, to store the elements in the order (8,7,6,5,4,3,2,1) in D.

/* Assume D is a Queue and S is a Stack */

// Step 1: Move elements from D to S
while (!D.isEmpty()) {
    S.push(D.dequeue());
}

// Step 2: Move elements from S back to D
while (!S.isEmpty()) {
    D.enqueue(S.pop());
}

Q7. Suppose you have two nonempty stacks S and T and an empty queue D. Describe how to use D so that S stores all the elements of T below all of its original elements, with both sets of elements still in their original order.

A solution. There can be others:

            //assuming S, T are stacks and D is a Queue
            D.enqueue(T.pop())
            D.enqueue(T.pop())
            T.push(S.pop())
            T.push(S.pop())            
            T.push(S.pop())
            T.push(D.dequeue())
            S.push(D.first())
            S.push(T.top())
            D.enqueue(T.pop())
            S.push(T.pop())
            S.push(T.pop())
            S.push(T.pop())
            S.push(D.dequeue())
            S.push(D.dequeue())

Q8. Suppose you have a non-empty Queue Q of type integers. Write a method that searches and removes value X in Q. Make sure the order of items in the queue are unchanged. If X is not found the method returns false, otherwise true.