Stacks: Last In, First Out

If you have ever hit Ctrl+Z to undo a mistake, clicked the back button in your browser, or watched a recursive function unspool in a debugger, you have already used a stack. The stack data structure is everywhere, both in the software you build and in the systems that run it.

Stacks are also one of the most common data structures in coding interviews. They show up in matching problems, parsing problems, "next greater element" problems, and dozens more. The good news is that the core concept is dead simple. Once you internalize LIFO ordering and the four fundamental operations, you can tackle the whole family of stack interview problems.

What is a stack?

A stack is a linear data structure where elements are added and removed from the same end, called the top. The element you added most recently is always the one that comes off first. That ordering principle has a name: LIFO, which stands for Last In, First Out.

Picture a stack of plates at a cafeteria. You put a clean plate on top. When someone needs a plate, they grab the one on top. The plate that was placed most recently is the first one taken. The plate at the very bottom has been sitting there the longest and will be the last one removed.

That is the entire mental model. There is no random access, no peeking at the middle, no jumping to the bottom. You interact with the top, and only the top.

The four stack operations

Every stack supports four operations, and they are all O(1):

That is a remarkably clean interface. No operation is worse than constant time. No matter how many elements are in the stack, push, pop, peek, and isEmpty all take the same amount of time.

Let's watch them in action. We will push three values, peek at the top, then pop everything off to see LIFO ordering play out.

Notice the key takeaway: 10 was the first element pushed and the last one popped. 30 was the last pushed and the first popped. That is LIFO in a nutshell.

Implementing a stack

You can implement a stack in two main ways: with an array (or dynamic array) or with a linked list. Both give you O(1) operations. The choice comes down to tradeoffs around memory and worst-case guarantees.

Array-based stack

In most languages, a dynamic array is the simplest and most practical stack implementation. In Python, a plain list works perfectly:

stack = []
stack.append(10)   # push
stack.append(20)   # push
stack.append(30)   # push

top = stack[-1]    # peek: 30
val = stack.pop()  # pop: 30
# stack is now [10, 20]

append() adds to the end (the "top"), and pop() removes from the end. Both are amortized O(1). The "amortized" part matters: occasionally, the underlying array needs to resize (allocate a bigger block and copy everything), which costs O(n). But that happens so rarely that averaged across all operations, each push is still constant time.

In JavaScript, you would use an array with push() and pop(). In Java, ArrayDeque is preferred over Stack (which is synchronized and outdated). In C++, std::stack wraps a deque by default.

Linked-list-based stack

You can also build a stack by inserting and removing at the head of a linked list. Every operation is O(1) with no amortization needed, because there is no array to resize.

class Node:
    def __init__(self, val, next_node=None):
        self.val = val
        self.next = next_node

class LinkedStack:
    def __init__(self):
        self.head = None

    def push(self, val):
        self.head = Node(val, self.head)

    def pop(self):
        if not self.head:
            raise IndexError("pop from empty stack")
        val = self.head.val
        self.head = self.head.next
        return val

    def peek(self):
        if not self.head:
            raise IndexError("peek at empty stack")
        return self.head.val

    def is_empty(self):
        return self.head is None

Each node holds a value and a pointer to the node below it. Pushing creates a new node that points to the current head. Popping removes the head and follows the pointer to the next node.

Which implementation should you use?

For interviews and most real-world code: use the array-based approach. It is simpler, uses less memory per element (no node/pointer overhead), and benefits from CPU cache locality since elements are stored contiguously. The linked-list version is useful when you need strict O(1) worst-case per operation (no amortized resizing) or when memory allocation patterns make contiguous storage impractical.

Real-world uses for stacks

Stacks are not just a textbook concept. They power fundamental features in the software and systems you use every day.

The call stack

When a program calls a function, the runtime pushes a stack frame onto the call stack. That frame holds the function's local variables, parameters, and the return address. When the function finishes, its frame is popped, and execution returns to the caller. Recursive functions keep pushing frames until they hit the base case, then pop them all off as each call returns.

This is why infinite recursion causes a stack overflow: the call stack runs out of space because frames keep getting pushed with nothing popping them.

Undo and redo

Text editors, drawing apps, and IDEs use stacks for undo/redo. Every action you take gets pushed onto an undo stack. When you press Ctrl+Z, the most recent action is popped and reversed. Some implementations push undone actions onto a separate redo stack so you can redo them too.

Browser back button

Your browsing history is a stack. Every page you visit gets pushed. When you click back, the current page is popped, and you see the previous one. Forward navigation works like a redo stack.

Expression parsing

Compilers and calculators use stacks to evaluate mathematical expressions and convert between infix (3 + 4), postfix (3 4 +), and prefix (+ 3 4) notation. The shunting-yard algorithm for parsing expressions relies on an operator stack to handle precedence and associativity.

Depth-first search (DFS)

DFS on a graph or tree can be implemented iteratively by replacing the implicit call stack with an explicit stack. You push neighbors onto the stack and pop them off to visit, exploring as deep as possible before backtracking.

When to use a stack

Reach for a stack when you see any of these patterns in a problem:

• Matching or validating nested structures. Parentheses, brackets, HTML tags, or any scenario where openers and closers must be properly paired.
• Processing elements in reverse order. Stacks naturally reverse the order of elements. If you push A, B, C, you pop C, B, A.
• Tracking "most recent" state. When you need to remember the most recent context and discard it once it is resolved (backtracking, undo, DFS).
• Finding the next or previous greater/smaller element. The monotonic stack pattern maintains a stack sorted in a specific order to answer "next greater" queries in O(n).
• Converting recursion to iteration. Any recursive algorithm can be converted to an iterative one using an explicit stack.

If a problem gives you a sequence and asks you to process items where the most recent item matters most, a stack is almost certainly the right tool.

Stack interview problems: the essential list

Below are the stack problems every developer should know. Each one teaches a different way to leverage LIFO ordering. If you can solve these fluently, you will be prepared for the vast majority of stack questions that come up in interviews.

Matching and validation

The most classic use of a stack: checking whether openers and closers are properly nested.

• Valid Parentheses - Push every opening bracket. When you see a closing bracket, pop the top and check if they match. If the stack is empty at the end, the string is valid. This is the first stack problem you should know cold.

Monotonic stack

The monotonic stack pattern keeps the stack sorted in increasing or decreasing order. As you iterate through an array, you pop elements that violate the ordering, which lets you efficiently answer "next greater" or "next smaller" questions.

• Daily Temperatures - For each day, find how many days until a warmer temperature. A monotonic decreasing stack processes the entire array in O(n), making it a perfect introduction to this pattern.
• Trapping Rain Water - Calculate how much rainwater gets trapped between bars. This problem can be solved with a stack that tracks bars in decreasing order, popping whenever a taller bar appears to compute trapped water.

Design problems

• Min Stack - Design a stack that supports push, pop, top, and getMin, all in O(1). The trick is maintaining a parallel structure that tracks the minimum value at each level of the stack.

Patterns guide

For a comprehensive breakdown of every stack technique (bracket matching, monotonic stacks, expression evaluation, state save/restore), check out the full guide:

• Stack Patterns - The complete playbook for recognizing and applying stack-based techniques across any problem.

Wrapping up

The stack data structure is one of the simplest you will ever learn. Four operations, all O(1), and a single ordering principle: LIFO. But do not let that simplicity fool you. Stacks power the call stack that runs every program, the undo feature you use daily, and an entire family of interview problems from parentheses matching to monotonic stack queries.

The key to mastering stacks is not understanding the theory (you already have that). It is building fluency by writing the code from scratch, repeatedly, until pushing, popping, and recognizing stack problems becomes second nature.