1. Describe the state of a stack and the output after each of the following stac

Question

1. Describe the state of a stack and the output after each of the following stack operations, starting with an empty stack: push(2), push(4), pop(), push(5), top(), pop(), isempty(), pop().

2. Describe the state of a queue and the output after each of the following queue operations, starting with an empty queue: enqueue(5), enqueue(2), dequeue(), enqueue(1), dequeue(), dequeue(), size().

3. Suppose you have a queue Q containing the number (1,2,3,4,5), in this order. Suppose you also have an empty stackS. Give a sequence of operations that uses only the stack S and the queue Q (and no other variables or objects) and results in the queue Q storing the number (4,5,3,2,1).

4. Describe a recursive algorithm for reversing a linked list. Please provide pseudocode.

5. Explain how you can implement all functions of the stack ADT using two queues. Specifically, given two queues Q1and Q2 with the standard operations (enqueue, dequeue, isempty, size), describe how you can implement the standard operations (pop, push, top, isempty, size) of a stack S. What is the time complexity for pop and push respectively?

6. Describe a recursive algorithm for counting the depth of a binary tree. The depth is the maximum length of a path from the root to a leaf. For example, the depth of a tree with a single root node A is 1. If the root node A has a left branch “A to B to C” and a right branch “A to D”, then the depth of the tree is 3.

Please shows steps. Appreicate any help, thanks.

Explanation / Answer

4.is empty() is to Check the stack is empty
Push (2)2

push(4)42

pop () . 2 push(5) 52 top() 5 pop() 2  

isempty() pop().

2 queue

2

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.