What Is a Stack? The Data Structure Behind Half Your Interview Problems

You hit Ctrl+Z. Your last edit disappears. Hit it again. The one before that. You can keep going backward, but only in the exact reverse order you made changes.

That's a stack data structure. You've been using one all day without thinking about it.

The last item in is always the first item out. This is called LIFO, Last In First Out, and the simplicity is exactly why stacks appear everywhere: your editor's undo history, the call stack executing your code right now, the browser's back button, and a suspicious number of interview problems you'll see in the next few months.

Three Operations. That's It.

A stack has three core operations:

• push(item) adds an item to the top
• pop() removes and returns the item at the top
• peek() looks at the top item without removing it

Some implementations add isEmpty(). Also O(1).

That's the whole interface. No random access. You can't ask for the third item from the bottom. You can't peek at the second item. You only ever see the top, like a stack of plates at a buffet where you are legally obligated to take from the top and aren't allowed to question why.

LIFO in Practice

Say you're navigating pages: Home, Blog, About, Contact. You push each one as you go.

push("Home")    → [Home]
push("Blog")    → [Home, Blog]
push("About")   → [Home, Blog, About]
push("Contact") → [Home, Blog, About, Contact]  ← top

Hit back twice:

pop() → "Contact"   [Home, Blog, About]
pop() → "About"     [Home, Blog]

You're back at Blog. The browser doesn't care what page you want. It cares what you saw most recently.

Push adds to the top. Pop removes from the top. Nothing else is accessible.

Arrays Do the Work

Arrays are the standard backing structure for a stack. Push to the end and pop from the end. Both operations touch only the tail, so they're O(1).

Here's a minimal implementation in Python:

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def size(self):
        return len(self._items)

And in TypeScript:

class Stack<T> {
  private items: T[] = [];

  push(item: T): void {
    this.items.push(item);
  }

  pop(): T {
    if (this.isEmpty()) throw new Error("Stack is empty");
    return this.items.pop()!;
  }

  peek(): T {
    if (this.isEmpty()) throw new Error("Stack is empty");
    return this.items[this.items.length - 1];
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }

  size(): number {
    return this.items.length;
  }
}

In practice you rarely build this from scratch. Python lists are stacks already (append() and pop()). Java uses Deque<Integer> stack = new ArrayDeque<>(), skip the legacy Stack class, which has been deprecated in spirit since Java 1.1 shipped it as a subclass of Vector and nobody has forgiven it since. JavaScript and TypeScript use arrays directly. Go uses a slice. Same pattern everywhere.

Linked lists can back a stack too, with push and pop at the head for true O(1) with no resize cost. In practice, arrays win on cache locality and simplicity. Linked lists win on... they don't, really. Arrays win.

Push is O(1). Mostly.

Operation	Time	Space
push	O(1) amortized	O(1)
pop	O(1)	O(1)
peek	O(1)	O(1)
search	O(n)	O(1)

The stack itself holds O(n) space for n elements.

Push is O(1) amortized, not O(1) worst-case. When the backing array fills up, it doubles and copies everything, costing O(n) for that one operation. Averaged across all the pushes that led you there, the per-push cost stays constant. This is the same trick every dynamic array uses. "O(1) push" is accurate enough for interviews, but "O(1) amortized" signals you know why it works.

For the formal proof and the full language-by-language breakdown, see the stack data structure deep dive.

You've Already Been Using the Call Stack

Every time you write a recursive function, you're using a real stack without touching it directly.

The call stack is an actual stack in memory, managed by your OS and runtime. When you call a function, a frame gets pushed. That frame holds local variables, the return address, and the saved state of the caller. When the function returns, the frame pops and execution resumes where the caller left off.

This is why recursion has a depth limit. Python hits RecursionError at 1,000 frames by default. The stack lives in a fixed memory region, typically 8MB on Linux and macOS. When that fills up, you get a stack overflow.

That error name sounds familiar, right? The error came first. The website was named after it. You've been using a site named after the exact moment a recursive function eats all the OS memory and the process dies ungracefully. Silicon Valley has a thing about naming products after catastrophic failures.

Converting recursion to iteration moves the stack from OS-managed memory to heap-allocated memory. The algorithm is identical. You're just swapping a hard 8MB limit for a much larger budget, which is the same reason people move out of their parents' house.

Why Interviewers Love This Structure

Stacks model the "undo the last thing" pattern, and a surprising number of problems reduce to exactly that shape.

When you see nesting, matching, or anything where the most recently seen element determines the answer, a stack is almost always the right tool. Four patterns are worth knowing cold.

Push on Open, Pop on Close

The classic: valid parentheses. Push every opening bracket. When you see a closing bracket, pop the top and check for a match. Stack empty when you expect a match, or leftovers at the end? Invalid.

def is_valid(s: str) -> bool:
    stack = []
    matching = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in '({[':
            stack.append(char)
        elif char in matching:
            if not stack or stack[-1] != matching[char]:
                return False
            stack.pop()

    return len(stack) == 0

This extends to HTML tag validation, JSON bracket checking, and arithmetic expression parsing. The structure never changes: push on open, validate-and-pop on close.

Swap the Runtime Stack for Your Own

Recursive DFS and iterative DFS are the same algorithm. The difference is which stack does the work.

def dfs_iterative(root):
    if not root:
        return []

    result = []
    stack = [root]

    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

    return result

Push right before left so left gets processed first (last in, first out). This is iterative preorder traversal in its most direct form. Inorder and postorder follow the same shape with a bit more bookkeeping.

The Monotonic Trick

A monotonic stack maintains elements in strictly increasing or decreasing order. When you push a new element, you first pop everything that violates the constraint. The payoff: for each element, you can find the next greater element or previous smaller element in O(n) total time, without any nested loops.

def next_greater_element(nums: list[int]) -> list[int]:
    result = [-1] * len(nums)
    stack = []  # stores indices

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result

Daily Temperatures (LeetCode 739) and Largest Rectangle in Histogram (LeetCode 84) are the two canonical problems. Largest Rectangle in Histogram is genuinely cruel, but it shows up, so learn it. The monotonic stack pattern gets its own deep treatment elsewhere because it deserves one.

Track Your Choices While Backtracking

When you explore a path and need to undo your last move, a stack tracks your choices. Push the current state when you go deeper, pop when you backtrack. Every maze solver, every permutation generator, every "find all valid paths" problem is depth-first search through a state space doing exactly this, whether the stack is explicit or borrowed from the runtime.

Think of it as Ctrl+Z for your algorithm.

How to Spot a Stack Problem Before You Write a Line

Three signals point toward a stack:

1. Nesting or matching. Parentheses, tags, brackets. Anything that opens and closes, where the most recently opened must close first.

2. Reverse order processing. A stack naturally reverses sequences. Undo history, backtracking, postfix expression evaluation.

3. "Most recent" determines the answer. If the relevant context at each step is whatever you saw most recently, a stack captures that relationship cleanly.

Problems that don't fit: they need random access (use an array or hash map), they process in arrival order (use a queue), or the relevant history grows without any expiration. See stack vs queue for a direct comparison of when each fits.

Five Problems That Cover the Full Pattern Range

Solve these before your interview:

• Valid Parentheses (LeetCode 20): the baseline
• Min Stack (LeetCode 155): maintain extra state alongside the stack
• Daily Temperatures (LeetCode 739): monotonic stack introduction
• Largest Rectangle in Histogram (LeetCode 84): the hardest common stack problem
• Decode String (LeetCode 394): nested structure with explicit push/pop of counts

Once you can solve these without hints, you have enough pattern fluency to handle most stack problems in an interview. The hard part is recognizing that a stack is the right tool, not writing the implementation. The code is simple. The recognition under pressure is not.

For a curated set ordered by difficulty, see top stack interview problems.

Practice the Recognition Out Loud

Reading a solution is different from producing one under pressure. Stacks are pattern-recognition problems: once you see the opening/closing structure, the implementation follows almost mechanically. But saying "this problem involves nested structure, so I'll use a stack to track what's opened" is a skill you build through practice, not through reading.

SpaceComplexity runs voice-based DSA mock interviews where you explain your reasoning in real time. For stack problems specifically, the narration matters as much as the code. An interviewer watching you push and pop needs to hear why you chose that structure, not just see it happen.

Further Reading

• Stack (abstract data type) -- Wikipedia
• Stack Data Structure -- GeeksforGeeks
• std::stack -- cppreference
• Using Lists as Stacks -- Python docs
• ArrayDeque -- Java SE documentation