Success TrackerSuccess Tracker
Log inSign up

GATE CS 2024 Set 2 — Question 48

MSQ+2 / -0HardStack OperationsStacks & QueuesProgramming & Data Structures

Programming & Data Structures → Stacks & Queues → Stack Operations

Last updated

Question

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.
Diagram showing Stack S1 with elements 400 (Top), 300, 200, 100 and an empty Stack S2
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?
A.
100, 200, 400, 300
B.
200, 300, 400, 100
C.
400, 200, 100, 300
D.
300, 200, 400, 100

Correct answer

(B) 200, 300, 400, 100; (C) 400, 200, 100, 300; (D) 300, 200, 400, 100

Solution

The initial state of Stack S1 is [100,200,300,400][100, 200, 300, 400] where 400400 is at the top. Stack S2 is empty with capacity 22. S1 has capacity 44.
Let's analyze each option:
(A) 100, 200, 400, 300
To output 100100 first, we must pop 400,300,200400, 300, 200 from S1 and store them in S2. This requires S2 to hold 33 elements. Since S2 capacity is 22, this is impossible.
(B) 200, 300, 400, 100
1.PushToS2 (400). S1: [100,200,300][100, 200, 300], S2: [400][400].
2.PushToS2 (300). S1: [100,200][100, 200], S2: [400,300][400, 300]. (S2 is full).
3.GenerateOutput (200). Output: 200. S1: [100][100].
4.PushToS1 (300). S1: [100,300][100, 300], S2: [400][400].
5.GenerateOutput (300). Output: 300. S1: [100][100].
6.PushToS1 (400). S1: [100,400][100, 400], S2: [][].
7.GenerateOutput (400). Output: 400. S1: [100][100].
8.GenerateOutput (100). Output: 100. S1: [][].
This sequence is possible.
(C) 400, 200, 100, 300
1.GenerateOutput (400). Output: 400. S1: [100,200,300][100, 200, 300].
2.PushToS2 (300). S1: [100,200][100, 200], S2: [300][300].
3.GenerateOutput (200). Output: 200. S1: [100][100].
4.GenerateOutput (100). Output: 100. S1: [][].
5.PushToS1 (300). S1: [300][300], S2: [][].
6.GenerateOutput (300). Output: 300. S1: [][].
This sequence is possible.
(D) 300, 200, 400, 100
1.PushToS2 (400). S1: [100,200,300][100, 200, 300], S2: [400][400].
2.GenerateOutput (300). Output: 300. S1: [100,200][100, 200].
3.GenerateOutput (200). Output: 200. S1: [100][100].
4.PushToS1 (400). S1: [100,400][100, 400], S2: [][].
5.GenerateOutput (400). Output: 400. S1: [100][100].
6.GenerateOutput (100). Output: 100. S1: [][].
This sequence is possible.
Thus, options (B), (C), and (D) can be generated.

More questions on Stacks & Queues

2024 Set 2 Q13Consider the following C program. Assume parameters to a function are evaluated from right to left.…2024 Set 2 Q17Let AA be the adjacency matrix of a simple undirected graph GG. Suppose AA is its own inverse.…2024 Set 1 Q17Given an integer array of size NN, we want to check if the array is sorted (in either ascending or…2024 Set 1 Q18Consider the following C program: [code] Which one of the following statements is CORRECT?2024 Set 1 Q19Consider the following C program: [code] Assume that the input to the program from the command line…

Practice GATE CS PYQs with adaptive difficulty

Timed practice, skill tracking, and AI explanations — free to start.

Start practicing free