Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of…
2024
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.
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
Attempted by 304 students.
Show answer & explanation
Correct answer: B, C, D
Correct output sequences (that can be generated with the given operations and capacities): 200, 300, 400, 100; 400, 200, 100, 300; 300, 200, 400, 100.
Why the sequence 100, 200, 400, 300 is impossible:
To output 100 first you must remove the three elements above it in the first stack. The only place to hold removed elements is the second stack, which has capacity 2. Because you cannot hold all three elements outside the first stack at once and you cannot output them before 100 (the required order), there is no valid sequence of allowed operations that exposes 100 as the top and outputs it first.
Feasible sequences and one possible set of operations for each:
200, 300, 400, 100 — One possible operation sequence:
PushToS2 (move 400 to the second stack).
PushToS2 (move 300 to the second stack).
GenerateOutput (pop 200 from the first stack and output 200).
PushToS1 (move 300 back to the first stack) then GenerateOutput (output 300).
PushToS1 (move 400 back to the first stack) then GenerateOutput (output 400).
GenerateOutput (output the remaining 100).
400, 200, 100, 300 — One possible operation sequence:
GenerateOutput (pop 400 and output it).
PushToS2 (move 300 to the second stack).
GenerateOutput (pop 200 and output it).
GenerateOutput (pop 100 and output it).
PushToS1 (move 300 back) then GenerateOutput (output 300).
300, 200, 400, 100 — One possible operation sequence:
PushToS2 (move 400 to the second stack).
GenerateOutput (pop 300 and output it).
GenerateOutput (pop 200 and output it).
PushToS1 (move 400 back) then GenerateOutput (output 400).
GenerateOutput (output the remaining 100).
A video solution is available for this question — log in and enroll to watch it.