GATE 2026 CS (CS2) – Question 50
Consider a stack $S$ and a queue $Q$, both initially empty and each capable of storing ten elements. The elements 1, 2, 3, 4, and 5 arrive one by one in that order. Each arriving element is assigned either to $S$ or to $Q$. After all five elements are stored, the output is generated by first emptying the stack completely and then emptying the queue completely. The output obtained is `4 3 1 2 5`. Which of the following options is/are possible valid assignments of the elements?
Note: $xS$ means element $x$ is assigned to $S$, and $yQ$ means element $y$ is assigned to $Q$.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) 1S, 2Q, 3S, 4S, 5Q; (B) 1Q, 2Q, 3S, 4S, 5Q
Explanation
Because the stack is emptied before the queue, the first part of the output must come from the stack in reverse insertion order. To produce `4 3 1`, the elements assigned to the stack must have been pushed in the order 1, 3, 4. The remaining elements then emerge from the queue as `2 5`. Option (A) achieves exactly this. Option (B) also works because the stack contains 3 and 4, producing `4 3`, and the queue contains 1, 2, 5, producing `1 2 5`; together they give `4 3 1 2 5`. Options (C) and (D) produce different prefixes. Therefore, the valid assignments are (A) and (B).