Recognize a LIFO dependency
Updated
A LIFO dependency is: the thing you must finish next is the most recently started unfinished thing. Matching brackets, nested undo, next-greater waiters, DFS leftover work. If the next finish is the oldest, you wanted a queue.
What to focus on
Ask: can a later item resolve an earlier one before resolving the ones in between? If no, stack. If yes and the earliest waits first, queue.
Worked examples
brackets
s = "([])"- inner must close before outer
Result: LIFO
queue counterexample
a = [4, 1, 9], serve oldest 4 first- FIFO
Result: not a stack
next greater waiters
a = [2, 1, 3]- 1 is more recent waiter than 2
- 1 resolves first when 3 arrives
Result: LIFO waiters
Try it
Write chooseAdt(kind). kind is "brackets", "line", or "nextGreater". Return "stack" or "queue". s = \"([])\" → LIFO. a = [4, 1, 9], serve oldest 4 first → not a stack. a = [2, 1, 3] → LIFO waiters.
Inputs are well-formed: matching brackets, a non-empty line, a non-empty array. Choose stack vs queue.