GATE CS 2022 Q.62: Stacks and Queues

Consider the queues Q1 containing four elements and Q2 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 Q1 required to place the elements of Q1 in Q2 in reverse order (shown as the Final State in the figure) without using any additional storage is___________.

Initial State showing queue Q1 with elements 1, 2, 3, 4 from Head and empty queue Q2; Final State showing empty queue Q1 and queue Q2 with elements 4, 3, 2, 1 from Head.

Your answer

Official answer and solution

Official answer: 0
From: Official GATE 2022 answer key

Note on this question

Reversing the elements of a FIFO queue into another FIFO queue without any auxiliary storage (not even a scalar variable) is impossible. The official answer key awards 0.

Solution

Analyze the structural invariants of queue operations without auxiliary storage.

We are given two FIFO queues $Q_1$ and $Q_2$ , where $Q_1 = [1, 2, 3, 4]$ and $Q_2 = []$ , and no auxiliary storage is allowed (not even scalar temporary variables).

In a queue, elements enter at the rear and leave at the front (FIFO). Transferring elements from $Q_1$ to $Q_2$ via Enqueue(Q2, Dequeue(Q1)) preserves the FIFO order, producing $Q_2 = [1, 2, 3, 4]$ .

To reverse the order into $Q_2 = [4, 3, 2, 1]$ , at least one stack (LIFO) or intermediate storage mechanism is mathematically necessary. Since only $Q_1$ and $Q_2$ are available and no auxiliary memory exists, it is impossible to reverse the order of 4 elements.

Because no sequence of operations can achieve the requested reversal, the minimum number of enqueue operations on $Q_1$ is 0, which is the official answer awarded by GATE.

Final answer

Common trap

Assuming elements can be stored in local variables to rotate elements between queues.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 62 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source