Consider the queues Q1 containing four elements and Q2 containing none (shown…
2022
Consider the queues Q1 containing four elements and Q2 containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q,element) and Dequeue(Q). The minimum number of Enqueue operations on Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional storage is___________.
Attempted by 142 students.
Show answer & explanation
Correct answer: 0
Answer: 0
Reason / steps (one possible valid sequence): start Q1 = [a,b,c,d] (front→rear), Q2 = [].
Dequeue(Q1)→ a;Enqueue(Q2,a)
Q1 = [b,c,d], Q2 = [a]Dequeue(Q1)→ b;Enqueue(Q2,b)
Q1 = [c,d], Q2 = [a,b]Rotate Q2:
Dequeue(Q2)→ a;Enqueue(Q2,a)
Q1 = [c,d], Q2 = [b,a]Dequeue(Q1)→ c;Enqueue(Q2,c)
Q1 = [d], Q2 = [b,a,c]Rotate Q2:
Dequeue(Q2)→ b;Enqueue(Q2,b)
Q1 = [d], Q2 = [a,c,b]Dequeue(Q2)→ a;Enqueue(Q2,a)
Q2 = [c,b,a]Dequeue(Q1)→ d;Enqueue(Q2,d)
Q1 = [], Q2 = [c,b,a,d]Rotate Q2 three times:
Dequeue(Q2)→c;Enqueue(Q2,c)→ [b,a,d,c]Dequeue(Q2)→b;Enqueue(Q2,b)→ [a,d,c,b]Dequeue(Q2)→a;Enqueue(Q2,a)→ [d,c,b,a]
Now Q2 = [d,c,b,a] and Q1 = []. At no point did we perform an Enqueue on Q1 — only Enqueue(Q2) and Dequeue operations were used. Hence the minimum number of Enqueue operations on Q1 required is 0.
A video solution is available for this question — log in and enroll to watch it.