Stack

A stack is a linear data structure that follows Last In, First Out (LIFO) order:

  • You can only insert and remove at one end (the “top”).
  • The most recently pushed element is the first one to be popped.

Stacks are conceptually simple but extremely powerful in algorithms and system internals.

Core Operations

Typical stack API:

  • push(x) – add x to the top.
  • pop() – remove and return the top element.
  • peek() – return the top element without removing it.
  • isEmpty() – check if the stack is empty.

Implementation options:

  • Dynamic array (e.g. ArrayDeque in Java, vector/ArrayList).
  • Linked list (push/pop at head).

All core operations are O(1) amortized.

Real‑World Uses

Stacks appear in many places:

  • Call stack:
    • Function calls push stack frames; returns pop them.
  • Undo / redo:
    • Editors and IDEs push actions to a stack so they can be undone.
  • Parsing:
    • Matching parentheses, XML/HTML tags, arithmetic expression evaluation.

Understanding stacks helps you reason about recursion depth, iterative simulations of recursion, and backtracking.

Common Interview Patterns

Stacks show up whenever you see:

  • Matching or nested structures:
    • Valid parentheses, remove outer parentheses, decode string patterns.
  • Need to remember “previous context”:
    • Evaluate Reverse Polish Notation (RPN).
    • Simplify file paths (/a/./b/../c).
  • Monotonic stack problems:
    • Next greater element, daily temperatures, largest rectangle in histogram.

In many of these, the stack does not just store raw values but augmented information (e.g. (value, index) pairs).

Pitfalls

  • Forgetting to check for empty stack before popping.
  • Using recursion where an explicit stack would avoid stack overflow for large inputs.

In Java/Python interviews, a stack is often just:

  • Java: Deque<Integer> stack = new ArrayDeque<>();
  • Python: stack = [] with .append() / .pop().

As long as you keep operations at one end, you get the desired LIFO behavior with good performance.

Example: Valid Parentheses Check (Java)

Java
boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

This illustrates a classic stack use case: matching nested structures.