GATE CS 2022 Q52 — Arrays, Stacks and Queues

We can reverse the elements of $Q_1$ into $Q_2$ using $0$ Enqueue operations on $Q_1$. This is achieved by systematically transferring elements from $Q_1$ to $Q_2$ and rotating $Q_2$ using only its own Enqueue and Dequeue operations.

Let the initial state of $Q_1$ be $[1, 2, 3, 4]$ (where $1$ is at the front and $4$ is at the rear) and $Q_2$ be empty $[]$. We want the final state of $Q_2$ to be $[4, 3, 2, 1]$ (where $4$ is at the front and $1$ is at the rear).

The step-by-step process is as follows:

1. Insert 1st element:
   • $\text{Dequeue}(Q_1) \to 1$, $\text{Enqueue}(Q_2, 1)$. Now, $Q_2 = [1]$.
2. Insert 2nd element and rotate:
   • $\text{Dequeue}(Q_1) \to 2$, $\text{Enqueue}(Q_2, 2)$. Now, $Q_2 = [1, 2]$.
   • $\text{Dequeue}(Q_2) \to 1$, $\text{Enqueue}(Q_2, 1)$. Now, $Q_2 = [2, 1]$.
3. Insert 3rd element and rotate:
   • $\text{Dequeue}(Q_1) \to 3$, $\text{Enqueue}(Q_2, 3)$. Now, $Q_2 = [2, 1, 3]$.
   • $\text{Dequeue}(Q_2) \to 2$, $\text{Enqueue}(Q_2, 2)$. Now, $Q_2 = [1, 3, 2]$.
   • $\text{Dequeue}(Q_2) \to 1$, $\text{Enqueue}(Q_2, 1)$. Now, $Q_2 = [3, 2, 1]$.
4. Insert 4th element and rotate:
   • $\text{Dequeue}(Q_1) \to 4$, $\text{Enqueue}(Q_2, 4)$. Now, $Q_2 = [3, 2, 1, 4]$.
   • $\text{Dequeue}(Q_2) \to 3$, $\text{Enqueue}(Q_2, 3)$. Now, $Q_2 = [2, 1, 4, 3]$.
   • $\text{Dequeue}(Q_2) \to 2$, $\text{Enqueue}(Q_2, 2)$. Now, $Q_2 = [1, 4, 3, 2]$.
   • $\text{Dequeue}(Q_2) \to 1$, $\text{Enqueue}(Q_2, 1)$. Now, $Q_2 = [4, 3, 2, 1]$.

Throughout this entire process, we only performed $\text{Dequeue}$ operations on $Q_1$. No $\text{Enqueue}$ operations were performed on $Q_1$. Thus, the minimum number of $\text{Enqueue}$ operations on $Q_1$ is 0.