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 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
Answer: C. c a b
Explanation: With a stack, we cannot get 'c a b' because to pop 'c', 'a' and 'b' must be popped first. If 'b' is printed before 'a', 'a' is stuck in B until 'c' is handled? If 'c' is first, 'b' and 'a' are in stack B (b on top of a). So we must pop 'b' then 'a'. Output would be 'c b a'.