IAE Academy

GATE 2026 CS2 Q.50: solution and answer

GATE 2026 · CS2Q.50 · 2 marks · MSQ

Consider a stack S and a queue Q. Both of them are initially empty and have the capacity to store ten elements each. The elements 1, 2, 3, 4, and 5 arrive one by one, in that order. When an element arrives, it is assigned either to S (pushed on S) or to Q (enqueued to Q). Once all the five elements are stored, the output is generated in two steps. First, stack S is emptied by popping all elements. Then queue Q is emptied by dequeueing all elements. The output obtained by following this process is 4 3 1 2 5.

Given the output, the objective is to predict whether an element was assigned to S or Q.

Which of the following options is/are possible valid assignment(s) of the elements?

Note: In the options, the notation xS denotes that element x was assigned to S and yQ denotes that element y was assigned to Q.

  1. (A)

    1S, 2Q, 3S, 4S, 5Q

  2. (B)

    1Q, 2Q, 3S, 4S, 5Q

  3. (C)

    1Q, 2Q, 3Q, 4S, 5S

  4. (D)

    1S, 2S, 3S, 4Q, 5Q

See the question in the paper
GATE 2026 CS2 question 50Tap to open full size

Answer and solution

ANSWER

Options A and B are the possible valid assignments.

Official answer: A, BSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Since elements 1,2,3,4,5 arrive in strictly increasing order, whichever subset is pushed onto S is pushed in increasing order, so popping S produces that subset in strictly decreasing order.

  2. Whichever subset is enqueued into Q is dequeued in the same (arrival) order, so it comes out in strictly increasing order.

  3. The final output is (decreasing sequence popped from S) followed by (increasing sequence dequeued from Q), and together these two parts must partition {1,2,3,4,5} exactly, each element appearing once. So a valid assignment corresponds exactly to a way of splitting the printed output 4,3,1,2,5 into a decreasing prefix followed by an increasing suffix.

  4. Test split after position 2: prefix [4,3] is decreasing (4>3); suffix [1,2,5] is increasing (1<2<5) — valid. This means S={3,4} (pushed 3 then 4, popped 4,3) and Q={1,2,5} (enqueued/dequeued 1,2,5 in that order), giving 1Q,2Q,3S,4S,5Q — option B.

  5. Test split after position 3: prefix [4,3,1] is decreasing (4>3>1); suffix [2,5] is increasing (2<5) — valid. This means S={1,3,4} (pushed in arrival order 1,3,4, popped 4,3,1) and Q={2,5} (dequeued 2,5 in arrival order), giving 1S,2Q,3S,4S,5Q — option A.

  6. Check the remaining splits: after position 1, suffix [3,1,2,5] is not increasing (3>1) — fails. After position 4, prefix [4,3,1,2] is not decreasing (1<2) — fails. The whole sequence as an all-S split (k=5) is not decreasing throughout, and the all-Q split (k=0) is not increasing throughout. So k=2 and k=3 are the only valid splits.

  7. Directly verify option C (1Q,2Q,3Q,4S,5S): S={4,5} pushed 4 then 5, popped in order 5,4; Q={1,2,3} dequeued 1,2,3; combined output = 5,4,1,2,3, which does not match the given output 4,3,1,2,5 — option C is invalid.

  8. Directly verify option D (1S,2S,3S,4Q,5Q): S={1,2,3} pushed in order, popped 3,2,1; Q={4,5} dequeued 4,5; combined output = 3,2,1,4,5, which does not match 4,3,1,2,5 — option D is invalid.

  9. Therefore the possible valid assignments are exactly options A and B.

KEY IDEA

A push-then-pop-all sequence of the increasing arrival order 1..5 must come out strictly decreasing (LIFO reverses order), while an enqueue-then-dequeue-all sequence of the same increasing arrivals must come out strictly increasing (FIFO preserves order); so the full output is always a decreasing block (from S) immediately followed by an increasing block (from Q), and checking validity reduces to finding every way to split the printed output into such a decreasing-prefix / increasing-suffix pair.

WATCH OUT FOR

Trying to verify each option only by re-simulating it forward (push/pop, enqueue/dequeue) one at a time, which is correct but slow and error-prone under time pressure; the faster and more reliable route is to first characterize the output's required shape (decreasing-then-increasing split of {1,...,5} in arrival order) and then just check where the given output 4 3 1 2 5 can be split that way, which immediately rules out any option whose S-subset, if popped, would not sit at the front in decreasing order matching the given prefix.

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

More Linear structures questions