GATE CS 2026 Set 2 Q40 — Arrays, Stacks and Queues

To find the valid assignments, let us understand how the output is generated:

1. Stack $S$ (LIFO): If elements are pushed into $S$ in the order of their arrival, popping them all will output them in the reverse order of their arrival.
2. Queue $Q$ (FIFO): If elements are enqueued into $Q$ in the order of their arrival, dequeueing them all will output them in the same order as their arrival.

The final output is the concatenation of the popped elements from $S$ followed by the dequeued elements from $Q$:

We need the final output to be $43125$. Let us test each option:

Option A: $1 S, 2 Q, 3 S, 4 S, 5 Q$

• Elements assigned to $S$: $1, 3, 4$ (in arrival order)
• Elements assigned to $Q$: $2, 5$ (in arrival order)
• Output from $S$ (reversed): $4, 3, 1$
• Output from $Q$ (same order): $2, 5$
• Combined Output: $43125$ (Matches)

Option B: $1 Q, 2 Q, 3 S, 4 S, 5 Q$

• Elements assigned to $S$: $3, 4$ (in arrival order)
• Elements assigned to $Q$: $1, 2, 5$ (in arrival order)
• Output from $S$ (reversed): $4, 3$
• Output from $Q$ (same order): $1, 2, 5$
• Combined Output: $43125$ (Matches)

Option C: $1 Q, 2 Q, 3 Q, 4 S, 5 S$

• Elements assigned to $S$: $4, 5$ (in arrival order)
• Elements assigned to $Q$: $1, 2, 3$ (in arrival order)
• Output from $S$ (reversed): $5, 4$
• Output from $Q$ (same order): $1, 2, 3$
• Combined Output: $54123$ (Does not match)

Option D: $1 S, 2 S, 3 S, 4 Q, 5 Q$

• Elements assigned to $S$: $1, 2, 3$ (in arrival order)
• Elements assigned to $Q$: $4, 5$ (in arrival order)
• Output from $S$ (reversed): $3, 2, 1$
• Output from $Q$ (same order): $4, 5$
• Combined Output: $32145$ (Does not match)

Thus, the valid assignments are A and B.