Skip to content
GATETECH
Official PYQ · 2024Set 2 · Q38Arrays, Stacks and QueuesMSQ2 marks

GATE CS 2024 Set 2 Q38 — Arrays, Stacks and Queues

Explain with AI

​​​​​Let S1\mathrm{S} 1 and S2\mathrm{S} 2 be two stacks. S1\mathrm{S} 1 has capacity of 44 elements. S2\mathrm{S} 2 has capacity of 22 elements. S1\text{S1} already has 44 elements: 100,200,300100,200,300, and 400400, whereas S2\text{S2} is empty, as shown below.400(Top)300200100Stack S1Stack S2\underset{\Large{\text{Stack S1}}}{\begin{array}{|l|} \hline 400\text{(Top)} \\ \hline 300 \\ \hline 200 \\ \hline 100 \\ \hline \end{array}}\quad \qquad \underset{\Large{\text{Stack S2}}}{\begin{array}{|l|} \hline &&& \\ \hline &&& \\ \hline \end{array}}

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?

Select all correct options
View worked solution

Answer: B;C;D

To determine which sequences can be generated, we trace the operations while respecting the capacity constraints: S1S_1 has capacity 44 and S2S_2 has capacity 22.

  • Option A (100,200,400,300100, 200, 400, 300) is impossible:
    To output 100100 first, we must remove 400,300,400, 300, and 200200 from S1S_1. Since we cannot output them yet, they must be moved to S2S_2. However, S2S_2 has a capacity of only 22. After moving 400400 and 300300 to S2S_2, S2S_2 becomes full. Thus, 200200 cannot be moved, blocking access to 100100.
  • Option B (200,300,400,100200, 300, 400, 100) is possible:
    1. PushToS2 twice: S1=[100,200]S_1 = [100, 200], S2=[400,300]S_2 = [400, 300]
    2. GenerateOutput: Outputs 200200. (S1=[100]S_1 = [100])
    3. PushToS1: S1=[100,300]S_1 = [100, 300], S2=[400]S_2 = [400]
    4. GenerateOutput: Outputs 300300. (S1=[100]S_1 = [100])
    5. PushToS1: S1=[100,400]S_1 = [100, 400], S2=[]S_2 = []
    6. GenerateOutput: Outputs 400400. (S1=[100]S_1 = [100])
    7. GenerateOutput: Outputs 100100. (S1=[]S_1 = [])
  • Option C (400,200,100,300400, 200, 100, 300) is possible:
    1. GenerateOutput: Outputs 400400. (S1=[100,200,300]S_1 = [100, 200, 300], S2=[]S_2 = [])
    2. PushToS2: S1=[100,200]S_1 = [100, 200], S2=[300]S_2 = [300]
    3. GenerateOutput: Outputs 200200. (S1=[100]S_1 = [100], S2=[300]S_2 = [300])
    4. PushToS2: S1=[]S_1 = [], S2=[300,100]S_2 = [300, 100]
    5. PushToS1: S1=[100]S_1 = [100], S2=[300]S_2 = [300]
    6. GenerateOutput: Outputs 100100. (S1=[]S_1 = [], S2=[300]S_2 = [300])
    7. PushToS1: S1=[300]S_1 = [300], S2=[]S_2 = []
    8. GenerateOutput: Outputs 300300. (S1=[]S_1 = [])
  • Option D (300,200,400,100300, 200, 400, 100) is possible:
    1. PushToS2: S1=[100,200,300]S_1 = [100, 200, 300], S2=[400]S_2 = [400]
    2. GenerateOutput: Outputs 300300. (S1=[100,200]S_1 = [100, 200])
    3. GenerateOutput: Outputs 200200. (S1=[100]S_1 = [100])
    4. PushToS1: S1=[100,400]S_1 = [100, 400], S2=[]S_2 = []
    5. GenerateOutput: Outputs 400400. (S1=[100]S_1 = [100])
    6. GenerateOutput: Outputs 100100. (S1=[]S_1 = [])

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Arrays, Stacks and Queues questions