Skip to main content

DSAPath7 mincore

Stacks

A stack is a last-in, first-out container. The most recent item pushed is the first item popped, which makes stacks natural for parsing, recursion, undo systems, and depth-first search.

Why This Matters

Stacks model unfinished work. A function call stack remembers where to return. A parser stack remembers open delimiters. DFS uses a stack to follow one branch before backtracking.

Core Idea

The two primary operations are push(x) and pop().

OperationCost with array-backed stack
pushamortized O(1)O(1)
popO(1)O(1)
peek topO(1)O(1)
searchO(n)O(n)

Worked example: when checking parentheses in ([]), push opening brackets and pop when a closing bracket appears. A mismatch or empty stack means the string is invalid.

Common Mistakes

  • Using a stack when first-in, first-out order is required.
  • Forgetting underflow: popping an empty stack is an error.
  • Treating recursion as magic. Recursion is often an implicit stack of pending calls.

Exercises

  • Use a stack to validate ({[]}).
  • Explain how DFS uses a stack.
  • Convert a recursive factorial function into an explicit stack trace.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 10, 20.
  • MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.