GATE 2022 CS Q.62: solution and answer

GATE 2022 · CSQ.62 · 2 marks · NAT

Consider the queues $Q_{1}$ containing four elements 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 (shown as the Final State in the figure) without using any additional storage is ______.

GATE 2022 CS question 62: Two labeled box diagrams side by side. — Figure from the GATE 2022 CS paper. It is part of the question.

Answer and solution

ANSWER

Official answer: 0Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

The question counts only Enqueue operations performed on $Q_{1}$ . Enqueue operations on $Q_{2}$ and all Dequeue operations are free as far as the count is concerned. So we look for a method that never enqueues anything back into $Q_{1}$ .
Required final state: $Q_{2}$ read from head to tail is $4, 3, 2, 1$ . $Q_{1}$ gives up its elements only in the order $1, 2, 3, 4$ (head first), so each element has to be moved into place inside $Q_{2}$ as it arrives. To do this we rotate $Q_{2}$ : Dequeue its head and at once Enqueue that element back onto $Q_{2}$ . The element is held for only one step, just as in any transfer between the two queues, so no additional storage is used.
Move 1: Dequeue( $Q_{1}$ ) gives 1, then Enqueue( $Q_{2}$ , 1). Now $Q_{2} = [1]$ . No rotation is needed.
Move 2: Dequeue( $Q_{1}$ ) gives 2, then Enqueue( $Q_{2}$ , 2), so $Q_{2} = [1, 2]$ . Rotate $Q_{2}$ once (take 1 off the head and put it at the tail): $Q_{2} = [2, 1]$ .
Move 3: Dequeue( $Q_{1}$ ) gives 3, then Enqueue( $Q_{2}$ , 3), so $Q_{2} = [2, 1, 3]$ . Rotate $Q_{2}$ twice (move 2, then 1, to the tail): $Q_{2} = [3, 2, 1]$ .
Move 4: Dequeue( $Q_{1}$ ) gives 4, then Enqueue( $Q_{2}$ , 4), so $Q_{2} = [3, 2, 1, 4]$ . Rotate $Q_{2}$ three times (move 3, 2, 1 to the tail): $Q_{2} = [4, 3, 2, 1]$ , which is the Final State. $Q_{1}$ is empty.
Count: every Enqueue above was on $Q_{2}$ : $4$ transfers plus $0 + 1 + 2 + 3 = 6$ rotations, $10$ in total. The number of Enqueue operations on $Q_{1}$ is $0$ .
A count cannot be negative, so $0$ is the minimum. The minimum number of Enqueue operations on $Q_{1}$ is $0$ .

KEY IDEA

Only Enqueue operations on $Q_{1}$ are counted. Move each element of $Q_{1}$ straight into $Q_{2}$ , then rotate $Q_{2}$ (Dequeue from $Q_{2}$ , Enqueue back onto $Q_{2}$ ) until the new element reaches the head. All of the reordering happens inside $Q_{2}$ , so $Q_{1}$ is never enqueued into and the minimum is 0.

WATCH OUT FOR

Doing the reordering by rotating $Q_{1}$ to bring 4, then 3, then 2 to its head. That takes $3 + 2 + 1 = 6$ Enqueues on $Q_{1}$ and gives 6. The rotations can be done on $Q_{2}$ instead, where they do not count. A second mistake is counting every Enqueue on both queues (10) when the question asks only about $Q_{1}$ .

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

GATE 2022 CS Q.62: solution and answer

Answer and solution

More Linear structures questions