ITPEC FE Morning October 2022 Question 7

Stack-based rearrangement — find the minimum number of stacks to reorder input.

Input order: A, C, K, S, T
Required output: S, T, A, C, K

Key insight:
- S and T (input positions 4, 5) must be output first — they can go directly to output as they arrive
- A, C, K (input positions 1, 2, 3) must be output in their original order (A → C → K) after S and T
- A single stack reverses order (LIFO), so storing multiple items in one stack inverts their sequence
- To preserve the order A → C → K, each must be stored in its own stack

Simulation with 3 stacks:
- A arrives → push to Stack 1: [A]
- C arrives → push to Stack 2: [C]
- K arrives → push to Stack 3: [K]
- S arrives → output directly as S
- T arrives → output directly as T
- Pop Stack 1 → A
- Pop Stack 2 → C
- Pop Stack 3 → K

Result: S, T, A, C, K ✓

Why 2 stacks fail:
- A, C, K must all wait in stacks, then come out as A → C → K
- Any distribution across 2 stacks puts at least 2 items in one stack, reversing their order
- [A, C] + [K] → pops give C, A, K ✗
- [A] + [C, K] → pops give A, K, C ✗
- [A, K] + [C] → pops give K, A, C ✗

Why not others:
- (a) 1 — single stack reverses all stored elements
- (b) 2 — no valid distribution preserves A → C → K order
- (d) 4 — 3 stacks already suffice

Key rule: When items must be output in original (non-reversed) order after a delay, each item needs its own stack. Minimum stacks = length of the longest subsequence that must be preserved in input order.

AI-generated — may contain errors