10.1-7 Question: Show how to implement a stack using two queues. Analyze the run
ID: 3814309 • Letter: 1
Question
10.1-7
Question:
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
Answer:
We have two queues and mark one of them as active. PUSH queues an element on the active queue. POP should dequeue all but one element of the active queue and queue them on the inactive. The roles of the queues are then reversed, and the final element left in the (now) inactive queue is returned.
The PUSH operation is (1), but the POP operation is (n) where n is the number of elements in the stack.
I thought it would be O(1) and O(n), and not as shown above. Please help...
Explanation / Answer
In push operation, the new element is always enqueued to q1.
In pop() operation, if q2 is empty then all the elements except the last, are moved to q2.
Finally the last element is dequeued from q1 and returned.
push(s, x)
1) Enqueue x to q1 (assuming size of q1 is unlimited).
pop(s)
1) One by one dequeue everything except the last element from q1 and enqueue to q2.
2) Dequeue the last item of q1, the dequeued item is result, store it.
3) Swap the names of q1 and q2
4) Return the item stored in step 2.
// Swapping of names is done to avoid one more movement of all elements
// from q2 to q1.
In sort:
push:
enqueue in queue1
pop:
while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2
dequeue and return the last item of queue1, then switch the names of queue1 and queue2
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.