GATE 2022 CS – Question 62
Consider the queues $Q_1$ containing four elements (1, 2, 3, 4 with 1 at the head) and $Q_2$ 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 $Q_1$ required to place the elements of $Q_1$ in $Q_2$ in reverse order (final state of $Q_2$ from head: 4, 3, 2, 1) without using any additional storage is ___________.

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6
Explanation
Goal: move the contents of $Q_1=(1,2,3,4)$ (head first) into $Q_2$ so that $Q_2$ reads $4,3,2,1$ from the head. $Q_2$ is filled in the order **4, 3, 2, 1**, so we need the elements to be dequeued from $Q_1$ in that order.
Only `Enqueue` and `Dequeue` are allowed and no other storage. The only way to bring an element to the head of $Q_1$ is to **rotate**: dequeue the head and enqueue it again at the tail.
- To get 4 to the head of $(1,2,3,4)$: rotate 1, 2, 3 (**3 enqueues** on $Q_1$) giving $(4,1,2,3)$. Dequeue 4 into $Q_2$.
- To get 3 to the head of $(1,2,3)$: rotate 1, 2 (**2 enqueues**), giving $(3,1,2)$. Dequeue 3 into $Q_2$.
- To get 2 to the head of $(1,2)$: rotate 1 (**1 enqueue**), giving $(2,1)$. Dequeue 2 into $Q_2$.
- 1 is now alone; dequeue it into $Q_2$ (0 enqueues on $Q_1$).
Enqueues on $Q_1$: $3+2+1=\mathbf6$.