ITPEC FE Morning October 2022 Question 7
Five (5) characters, A, C, K, S, and T, are input in this order. When using stacks, what is the minimum number of stacks required to rearrange the characters and output S, T, A, C, and K, in this order? Here, when a pop operation is performed for any stack, the popped character always becomes an output. Also, characters cannot be moved between stacks.
Explanation
3 stacks — A, C and K must wait until S and T are out, and must then leave in their input order, so no two of them can share a stack.
S and T arrive after A, C and K but are output first, so A, C and K all have to be held in stacks while S and T pass through. A stack is last in, first out: if two of A, C and K sat in the same stack, the later one would be popped first, reversing their order. Since they must come out as A, C, K, each needs its own stack.
With 3 stacks: push A, C and K onto stacks 1, 2 and 3; push S onto any stack and pop it at once, then the same for T; finally pop stacks 1, 2 and 3 to output A, C, K.
Answer (c)
Why not others:
- •(a) 1 — one stack holding A, C and K would output them as K, C, A
- •(b) 2 — some stack must hold two of A, C, K, and those two come out reversed
- •(d) 4 — more than needed: S and T can each be pushed and popped straight away on a stack that is already in use
Key rule: A stack reverses whatever it holds, so items that must wait and then leave in their original order each need a separate stack.
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 FE past-paper collection or Report an issue.