Stack

A stack gives back the most recently added item first (last in, first out) and a queue gives back the oldest first (first in, first out); both do their core operations in O(1).

Push every opening bracket and, on each closing bracket, check that it matches the top of the stack; the string is valid only if every check passes and the stack ends empty.

Keep a stack whose values are always increasing or decreasing; when a new element breaks the order, everything it pops has just found its next greater (or smaller) element, giving O(n) for problems that look O(n^2).

Stacks turn arithmetic text into answers: postfix (RPN) needs one stack of numbers, and normal infix expressions need either a sign-aware number stack or two stacks (numbers and operators) to respect precedence and parentheses.

Design questions ask you to add a feature (like get_min in O(1)) or build one structure from another (a queue from two stacks); the trick is storing a little extra state per element or moving elements lazily so every operation stays O(1) or O(1) amortised.