18. Stack & Queue

A stack is last-in, first-out, like a pile of plates. A queue is first-in, first-out, like a line at a counter. A deque lets you add and remove at both ends. In Java, use ArrayDeque for all three; Stack and LinkedList are older and slower.

The big pattern here is the monotonic stack: keep the stack increasing (or decreasing), and every pop answers "next greater" or "next smaller" for the popped item. Each item is pushed and popped once, so it's O(n).