GATE CSE 2022 | Question: 52

Question

Consider the queues $Q_{1}$ containing four elements and $Q_{2}$ containing none (shown as the $\textsf{Initial State}$ in the figure). The only operations allowed on these two queues are $\textsf{Enqueue (Q, element)}$ and $\textsf{Dequeue (Q)}.$ The minimum number of $\textsf{Enqueue}$ operations on $Q_{1}$ required to place the elements of $Q_{1}$ in $Q_{2}$ in reverse order (shown as the $\textsf{Final State}$ in the figure) without using any additional storage is________________.

 

Comments

@tusharb @Abhrajyoti00 how we can consider size of Q2 > 4? w/o mentioning in qn?

and if in place of min , if max was asked then ans should be 6 in this case right?

---

@MANSI_SOMANI Max would be infinite
just keep on enque-ing and deque-ing in Q1 only, don’t put them in Q2

---

@JAINchiNMay right got it 

but how can we consider size of Q2>4 (as mentioned by @tusharb above but i think there is no need to take more than 4) w/o any mention in the qn? 

Answer 1

Caption

1) Transfer all data from Q1 to Q2 so here no need to Enqueue on Q1

2) Now Q2 is like Q1 and then apply recursive algo on Q2 . No need to apply any operation on Q1 

So Ans is Zero .

Comments

@Arjun sir why the final answer is given 3 here(thanks for correction)

Answer 2

“The minimum number of Enqueue operations on Q1 required to place the elements” 

E= Enqueue

D= Dequeue