Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry…
2008
Stack A has the entries a, b, c (with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B. An entry popped out of the stack B can be only be printed. In this arrangement, which of the following permutations of a, b, c are not possible?
- A.
b a c
- B.
b c a
- C.
c a b
- D.
a b c
Attempted by 450 students.
Show answer & explanation
Correct answer: C
To determine the impossible permutation, trace the stack operations.
Initial State: Stack A = [a, b, c] (a is top), Stack B = []. To print 'c' first, we must pop 'a' and 'b' from A into B.
1. Pop 'a' from A, push to B. Stack B = [a].
2. Pop 'b' from A, push to B. Stack B = [a, b] (b is top).
3. Pop 'c' from A, print 'c'. Stack B = [a, b] (b is top).
4. Next, we must pop from Stack B. Since 'b' is on top of 'a', 'b' must be printed before 'a'. The sequence becomes c, b, a.
5. The permutation 'c a b' requires printing 'a' before 'b' after 'c', which violates the LIFO property of Stack B.
Thus, 'c a b' is not possible.
A video solution is available for this question — log in and enroll to watch it.