The GATE Grind

GATE 2022 CS – Question 62

Programming and Data Structures · Stacks and Queues · 2 marks · Numerical answer

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 ___________.

Diagram for GATE 2022 CS question 62

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.

Enqueues on $Q_1$: $3+2+1=\mathbf6$.

More Stacks and Queues questions

All Stacks and Queues questions →