GATE CS 2024 Set 2 Q.48: Stacks and Queues

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 of capacity 4 containing 400 (Top), 300, 200, 100 from top to bottom, and empty Stack S2 of 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?

100, 200, 400, 300

200, 300, 400, 100

400, 200, 100, 300

300, 200, 400, 100

Official answer and solution

Official answer: B, C and D
From: Official GATE 2024 answer key

Solution

Check each candidate output sequence against the capacity limit of 2 on auxiliary stack S2.

(A) 100, 200, 400, 300 is IMPOSSIBLE: To output 100 first, all three elements above 100 (400, 300, 200) must be removed from S1 without being output, which would require holding $3$ elements in S2 simultaneously, violating S2's capacity of $2$ .
(B) 200, 300, 400, 100 is POSSIBLE:
1. PushToS2 (400), PushToS2 (300) $\implies S_2 = [400, 300\text{ (Top)}]$ , $S_1 = [100, 200\text{ (Top)}]$ .
2. GenerateOutput $\implies$ outputs 200.
3. PushToS1 (300), GenerateOutput $\implies$ outputs 300.
4. PushToS1 (400), GenerateOutput $\implies$ outputs 400.
5. GenerateOutput $\implies$ outputs 100.
(C) 400, 200, 100, 300 is POSSIBLE:
1. GenerateOutput $\implies$ outputs 400.
2. PushToS2 (300) $\implies S_2 = [300]$ , $S_1 = [100, 200\text{ (Top)}]$ .
3. GenerateOutput $\implies$ outputs 200.
4. GenerateOutput $\implies$ outputs 100.
5. PushToS1 (300), GenerateOutput $\implies$ outputs 300.
(D) 300, 200, 400, 100 is POSSIBLE:
1. PushToS2 (400) $\implies S_2 = [400]$ , $S_1 = [100, 200, 300\text{ (Top)}]$ .
2. GenerateOutput $\implies$ outputs 300.
3. GenerateOutput $\implies$ outputs 200.
4. PushToS1 (400), GenerateOutput $\implies$ outputs 400.
5. GenerateOutput $\implies$ outputs 100.

Final answer

Options (B), (C), (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 48 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source