ITPEC IP April 2024 Question 8
There is a device that stacks products from the bottom to the top, and removes the products sequentially from the top. There are only two (2) operations for this device.
Nothing is stacked at the start, and three (3) products arrive in the order A, B, then C. If only one (1) device is used, when the products are removed with POP operations, which of the following is an impossible order of removal?
Explanation
C, A, B — once C has come out first, B still lies on top of A, so A cannot come out before B.
The device is a stack: last in, first out. POP always removes the most recently pushed product still on the stack. The products arrive in the fixed order A, B, C, but a POP may be made between any two PUSHes. For C to come out first, A and B must already be stacked beneath it, B above A. After C is popped, B is on top, so the next POP gives B, never A.
Answer (c)
Why not others:
- •(a) A, B, C — possible: PUSH A, POP, PUSH B, POP, PUSH C, POP: each product is removed before the next arrives
- •(b) B, A, C — possible: PUSH A, PUSH B, POP, POP, PUSH C, POP
- •(d) C, B, A — possible: PUSH A, PUSH B, PUSH C, POP, POP, POP: all three stacked, then removed in reverse
Key rule: With one stack, the items still stacked below a popped item can only come out in reverse order of arrival, so an output in which an earlier item overtakes a later one still on the stack is impossible.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official IP past-paper collection or Report an issue.