Stack

Maintain a last-in-first-out structure to track state in reverse order or defer decisions until a matching event.

Maintain a last-in-first-out structure to track state in reverse order or defer decisions until a matching event.

The stack contains only elements that have not yet been resolved — each pop event is a completion signal.

LIFO order mirrors the nested or reversed structure of the problem — the most recent unmatched item is always on top.

A single linear pass suffices because each element is pushed and popped at most once, giving O(n) time.