Which of the following output permutations can be produced by a stack of…
2012
Which of the following output permutations can be produced by a stack of capacity 3 when the input sequence is 1, 2, 3, 4, 5?
Answer: A. 3, 2, 1, 5, 4; C. 3, 4, 5, 2, 1 — ConceptA stack follows the last-in, first-out (LIFO) rule: only the top item can be removed. To test an output permutation, push the next input items in order…
- A.
3, 2, 1, 5, 4
- B.
5, 4, 3, 2, 1
- C.
3, 4, 5, 2, 1
- D.
3, 4, 5, 1, 2
Attempted by 24 students.
Show answer & explanation
Correct answer: A, C
Concept
A stack follows the last-in, first-out (LIFO) rule: only the top item can be removed. To test an output permutation, push the next input items in order until the required output reaches the top, then pop it. The stack depth must never exceed its capacity.
Application
For 3, 2, 1, 5, 4: push 1, 2, 3; pop 3, 2, 1; then push 4, 5 and pop 5, 4. The maximum depth is 3.
For 5, 4, 3, 2, 1: producing 5 first requires 1, 2, 3, 4, 5 to be pushed before any pop, so the depth would be 5.
For 3, 4, 5, 2, 1: push 1, 2, 3 and pop 3; push and pop 4; push and pop 5; then pop 2 and 1. The maximum depth is 3.
For 3, 4, 5, 1, 2: after producing 3, 4, 5, the stack contains 1 below 2. LIFO makes 2 leave before 1, so 1 cannot be produced next.
Cross-check
The successful traces use only legal push/pop operations and never hold more than three items. The other traces either exceed capacity or request an item hidden below the stack top.
Therefore, the obtainable permutations are 3, 2, 1, 5, 4 and 3, 4, 5, 2, 1.