GATE 2024 CS (CS2) – Question 48
Let S1 and S2 be two stacks. S1 has capacity 4 and already holds 100, 200, 300, 400 (400 on top). S2 has capacity 2 and is empty. Operations: PushToS2 (pop from S1, push on S2), PushToS1 (pop from S2, push on S1), GenerateOutput (pop from S1 and output). Pop on an empty stack and push on a full stack are not allowed. Which of the following output sequences can be generated?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 200, 300, 400, 100; (C) 400, 200, 100, 300; (D) 300, 200, 400, 100
Explanation
S1 holds 100, 200, 300, 400 (400 on top, capacity 4). S2 is empty with capacity 2. Operations: move S1→S2, move S2→S1, output from top of S1.
- **(A) 100, 200, 400, 300 — impossible.** To output 100 first, 200, 300 and 400 must all be moved off S1, but S2 holds only 2.
- **(B) 200, 300, 400, 100 — possible.** Move 400→S2, 300→S2 (S2: 400, 300 with 300 on top). Output 200. Move 300→S1, output 300. Move 400→S1, output 400. Output 100.
- **(C) 400, 200, 100, 300 — possible.** Output 400. Move 300→S2. Output 200, output 100. Move 300→S1, output 300.
- **(D) 300, 200, 400, 100 — possible.** Move 400→S2. Output 300, output 200. Move 400→S1, output 400. Output 100.
Answer: B, C, D.