The GATE Grind

GATE 2024 CS (CS2) – Question 48

Programming and Data Structures · Stacks and Queues · 2 marks · Multiple select

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?

  1. 100, 200, 400, 300
  2. 200, 300, 400, 100
  3. 400, 200, 100, 300
  4. 300, 200, 400, 100

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 400, 200, 100, 300; (D) 300, 200, 400, 100

Explanation

S2 holds at most 2 items so 100 cannot be output before 200 and 300 are moved (A, B fail). For C: output 400, move 300 to S2, output 200, output 100, move 300 back, output 300. For D: move 400 to S2, output 300, output 200, move 400 back, output 400, output 100.