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?

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().

Q3. Implement a method with signature transfer(S, T) that transfers all elements from stack S onto stack T, so that the element that starts at the top of S is the first to be inserted onto T, and the element at the bottom of S ends up at the top of T.

Q4. 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().

Q5. 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.

Q6. 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.

Q7. 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.

Q8. Repeat Q7 for a queue.