Solve using algorithm
October 21, 2022
Essayheroes
- Suppose an initially empty stack S has executed a total of 25 push operations, 12 top operations, and 10 pop operations, 3 of which raised Empty errors that were caught and ignored. What is the current size of S ?
- Implement a function 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 .
- Implement a function that reverses a list of elements by pushing them onto a stack in one order, and writing them back to the list in reversed order.
- Suppose you have a deque D containing the numbers ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 ) , in this order. Suppose further that you have an initially empty queue Q . Give a code fragment that uses only D and Q (and no other variables) and results in D storing the elements in the order ( 1 , 2 , 3 , 5 , 4 , 6 , 7 , 8 )
- Repeat the previous problem using the deque D and an initially empty stack S .
- Suppose Alice has picked three distinct integers and placed them into a stack S in random order. Write a short, straight-line piece of pseudo-code (with no loops or recursion) that uses only one comparison and only one variable x , yet that results in variable x storing the largest of Alice’s three integers with probability 2 / 3. Argue why your method is correct.
- Show how to use the transfer function, described in Exercise R-6.3, and two temporary stacks, to replace the contents of a given stack S with those same elements, but in reversed order.
- In certain applications of the queue ADT, it is common to repeatedly dequeue an element, process it in some way, and then immediately enqueue the same element. Modify the ArrayQueue implementation to include a rotate( ) method that has semantics identical to the combination, Q.enqueue(Q.dequeue( )) . However, your implementation should be more efficient than making two separate calls (for example, because there is no need to modify size ).
