What is a Stack

A stack is a data structure that follows the LIFO principle: last in, first out. You can only add (push) and remove (pop) elements from one end — the top. Think of a stack of plates: you add plates to the top and take plates from the top. You cannot pull a plate from the middle.

How it works

A stack supports two primary operations, both O(1):

• Push — add an element to the top.
• Pop — remove and return the element from the top.

Most implementations also provide peek (view the top element without removing it) and isEmpty.

push(A)  push(B)  push(C)  pop()   pop()

  [C]            → returns C
  [B]     [B]      [B]     [B]    → returns B
  [A]     [A]      [A]     [A]     [A]

Stacks are typically implemented using an array (push appends, pop removes from the end) or a linked list (push prepends, pop removes the head). Array-based stacks are more common because of better cache performance.

The most important real-world stack is the call stack. Every time a function is called, a frame containing its local variables and return address is pushed onto the call stack. When the function returns, its frame is popped. This is why recursive functions can overflow the stack — each recursive call pushes another frame, and too many calls exhaust the available stack memory.

Other uses of stacks:

• Undo/redo — each action is pushed; undo pops the last action.
• Expression parsing — compilers use stacks to evaluate parenthesized expressions and convert between infix and postfix notation.
• DFS traversal — depth-first search in a graph uses a stack (explicitly or via recursion) to track which nodes to visit next.
• Backtracking — algorithms that explore and revert choices (maze solving, constraint satisfaction) use the stack's natural "undo last step" behavior.

Why it matters

Stacks are simple but pervasive. The call stack runs every program you write. DFS, expression evaluation, and backtracking all depend on LIFO ordering. Understanding stacks also explains stack overflows, recursion limits, and why iterative DFS can replace recursive DFS.

See How Arrays and Linked Lists Work for the underlying implementations.