Which of the following permutations can be obtained in the output (in the same…
1994
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?
- A.
3, 4, 5, 1, 2
- B.
3, 4, 5, 2, 1
- C.
1, 5, 2, 3, 4
- D.
5, 4, 3, 1, 2
Attempted by 178 students.
Show answer & explanation
Correct answer: B
Stacks operate on a Last-In-First-Out (LIFO) principle. To output 3, 4, 5 first from input 1-5, we push 1, 2, 3 and pop 3. Then push 4, pop 4; push 5, pop 5. The stack retains [1, 2] with 2 on top. LIFO requires popping 2 before 1, making the sequence 3, 4, 5, 2, 1 valid. Any permutation claiming 1 before 2 after these pops is impossible.
A video solution is available for this question — log in and enroll to watch it.