Consider six stack operations: pushing and popping each of A, B, and C exactly…
2010
Consider six stack operations: pushing and popping each of A, B, and C exactly once. The pushes must occur in the order push(A), then push(B), then push(C), although pops may be interleaved. For example, ACB can be a pop order via push(A), pop(A), push(B), push(C), pop(C), pop(B). Which of the following cannot be the pop order?
Answer: D. CAB — CONCEPTA stack follows the last-in, first-out (LIFO) rule: only the item at the top can be popped. If a later-pushed item remains above an earlier-pushed…
- A.
ABC
- B.
CBA
- C.
BAC
- D.
CAB
Attempted by 81 students.
Show answer & explanation
Correct answer: D
CONCEPT
A stack follows the last-in, first-out (LIFO) rule: only the item at the top can be popped. If a later-pushed item remains above an earlier-pushed item, the earlier item cannot be popped first.
Therefore, a requested pop order is feasible only when each requested item is at the top at that moment; pushes may be interleaved, but their relative order remains A, then B, then C.
APPLICATION
To attempt CAB, C must be popped first. Since A and B have not yet been popped, all three items must already have been pushed in the order A, B, C; C is then at the top.
After popping C, the remaining stack has A below B, so B is at the top.
CAB next requests A, but A cannot be popped while B remains above it. Thus CAB cannot be produced by a stack.
CROSS-CHECK AND CONTRAST
Each other offered order has a valid operation trace:
Pop order | Valid operation trace |
|---|---|
ABC | push(A), pop(A), push(B), pop(B), push(C), pop(C) |
CBA | push(A), push(B), push(C), pop(C), pop(B), pop(A) |
BAC | push(A), push(B), pop(B), pop(A), push(C), pop(C) |
Hence, the pop order that cannot occur is CAB.