IAE Academy

GATE 2024 CS2 Q.48: solution and answer

GATE 2024 · CS2Q.48 · 2 marks · MSQ

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.

Stack S1 (bottom to top): 100, 200, 300, 400 (Top)
Stack S2: empty (capacity 2)

Only the following three operations are available:

PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.

Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.

Which of the following output sequences can be generated by using the above operations?

GATE 2024 CS2 question 48: Two stack diagrams side by side.Tap to open full size
Figure from the GATE 2024 CS2 paper. It is part of the question.
Figure description

Two stack diagrams side by side. Left: Stack S1, drawn as a vertical box divided into 4 cells, bottom to top: 100, 200, 300, 400, with '400 (Top)' labeling the topmost cell, labeled 'Stack S1' below. Right: Stack S2, drawn as a vertical box with 2 empty cells (capacity 2), labeled 'Stack S2' below, currently empty.

  1. (A)

    100, 200, 400, 300

  2. (B)

    200, 300, 400, 100

  3. (C)

    400, 200, 100, 300

  4. (D)

    300, 200, 400, 100

Answer and solution

ANSWER

The output sequences achievable are (B) 200, 300, 400, 100; (C) 400, 200, 100, 300; and (D) 300, 200, 400, 100. (A) 100, 200, 400, 300 is not achievable.

Official answer: B, C, DSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

  1. Setup: S1 (bottom→top) = 100, 200, 300, 400 (top = 400), S2 is empty with capacity 2. GenerateOutput only removes S1's current top; to output an element buried under elements, those elements must first be moved off S1 via PushToS2, and S2 can hold at most 2 at a time.

  2. Option (A) 100, 200, 400, 300: outputting 100 first needs 400, 300 and 200 all cleared off S1's top beforehand, with none of them yet output — that means all three would have to sit in S2 at once, but S2's capacity is only 2. So (A) is impossible.

  3. Option (B) 200, 300, 400, 100: PushToS2 (400→S2), PushToS2 (300→S2; S2 = [400,300], full) → S1 top is now 200 → GenerateOutput gives 200. PushToS1 (300 back onto S1) → GenerateOutput gives 300. PushToS1 (400 back onto S1) → GenerateOutput gives 400. GenerateOutput gives 100. Result: 200, 300, 400, 100 — matches (B) exactly, so (B) is achievable.

  4. Option (C) 400, 200, 100, 300: GenerateOutput gives 400 (S1's initial top). PushToS2 (300→S2) → S1 top is now 200 → GenerateOutput gives 200. GenerateOutput gives 100 (S1 top after 200 removed). PushToS1 (300 back onto S1) → GenerateOutput gives 300. Result: 400, 200, 100, 300 — matches (C) exactly, so (C) is achievable.

  5. Option (D) 300, 200, 400, 100: PushToS2 (400→S2) → S1 top is now 300 → GenerateOutput gives 300. GenerateOutput gives 200 (new S1 top). PushToS1 (400 back onto S1) → GenerateOutput gives 400. GenerateOutput gives 100. Result: 300, 200, 400, 100 — matches (D) exactly, so (D) is achievable.

  6. Conclusion: (B), (C) and (D) are all achievable output sequences; (A) is not, since it would need 3 elements parked in a capacity-2 auxiliary stack simultaneously.

KEY IDEA

GenerateOutput can only remove S1's current top element. To output an element buried under others, those elements must first be moved off S1 via PushToS2 — but S2 holds at most 2 elements at a time, so at most 2 elements can be "parked" and later restored (via PushToS1) to reach an element beneath them.

WATCH OUT FOR

Assuming any permutation reachable by "pop some, push some" is achievable without tracking S2's capacity limit of 2 — this wrongly admits sequences (like A) that need three elements moved off S1 before the first output.

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

More Linear structures questions