Skip to main content

Stacks

A stack exposes the most recently pushed item first: last in, first out. Its minimal operations are push, pop, peek, and an emptiness check.

stack: list[str] = []
stack.append("first")
stack.append("second")
top = stack[-1]
removed = stack.pop()

Using the end of a dynamic array gives amortized O(1)O(1) push and O(1)O(1) pop/peek. A linked implementation can provide worst-case O(1)O(1) endpoint updates but adds one allocation and link per element.

Invariant​

Only the top is directly removable. Restricting access communicates unfinished work: the top often represents the most recent open delimiter, active search state, pending operator, or undoable action.

Common uses​

  • iterative depth-first search and backtracking;
  • expression parsing and delimiter matching;
  • undo histories and nested scopes;
  • simulating recursion when explicit control over state is useful.

The language runtime call stack is related but also stores return addresses, locals, and execution metadata; it is not merely a user-level value stack.

Failure and capacity​

Popping an empty stack is underflow and should have an explicit contract. A bounded stack can also overflow; a dynamic implementation instead faces memory allocation failure or policy limits.

Do not use front insertion/removal on a dynamic array to model a stack; it adds unnecessary shifts.

Source​