Stack

Last in, first out.

A stack is like a stack of plates: you add (push) to the top and remove (pop) from the top. The last plate you put on is the first one you take off.

• push — add to the top.
• pop — remove and return the top.
• peek/top — look at the top without removing it.

Implementation and uses.

A stack can be backed by a dynamic array (push/pop at the end) or a linked list (push/pop at the head). All core operations are O(1).

• Function call stack / recursion
• Undo/redo in editors
• Expression evaluation & balanced parentheses
• Backtracking (DFS, maze solving)
• Browser back button history

Depth, recursion, and pitfalls.

• Call stack & stack overflow — deep or infinite recursion exhausts the program's stack; convert to an explicit stack or use tail-call/iterative forms.
• DFS — an explicit stack replaces recursion for graph/tree depth-first traversal with controlled memory.
• Monotonic stack — keeps elements in sorted order to solve "next greater element" and histogram problems in O(n).
• Two-stack tricks — implement a queue with two stacks, or a min-stack tracking the minimum in O(1).