Stacks (LIFO)

A stack is one of those ideas you already use long before you formally learn it. Think about a stack of plates in a kitchen: you place the newest plate on top, and when you need one, you take the top plate off first. Or think about Ctrl+Z in an editor: the most recent edit gets undone first. The browser back button behaves similarly too: the page you visited most recently is the first one you return to.

That shared rule is the entire personality of the data structure: Last In, First Out (LIFO). The last thing you put in is the first thing that comes back out.

Stacks matter because this simple ordering shows up everywhere. Expression evaluation uses stacks. Undo/redo uses stacks. Depth-first search can use a stack. And perhaps most importantly, function calls use a stack under the hood. You already know the stack from recursion and the call stack in post 1 — now we are turning that vague idea into a concrete data structure you can implement and use on purpose.

Reader-wise, you are in a great spot for this post. You already know arrays, dynamic arrays, and the pointer mindset behind singly linked lists. A stack is not a brand-new storage mechanism; it is a discipline imposed on top of storage you already understand. That is why stacks are so useful: they are simple, strict, and fast.

What is a stack?

A stack is a linear data structure where all updates happen at one end only, called the top. You do not insert into the middle. You do not remove from the bottom. You interact only with the top.

That gives you three core operations:

• push(x): add x to the top
• pop(): remove and return the top element
• peek() or top(): look at the top element without removing it

Most stack APIs also include:

• isEmpty(): is the stack empty?
• size(): how many elements are in it?

The whole point is that these top-end operations are O(1). No shifting like array insertion at the front. No walking through nodes like linked-list traversal. Just add, remove, or inspect the top and move on.

That is why a stack is best thought of as an abstract data type (ADT). The important part is the behavior: “last in, first out” plus the small set of operations above. The underlying storage is secondary. You can build that interface using an array, a dynamic array, or a linked list. If the operations behave like a stack, then from the outside it is a stack.

flowchart TB
Top["Top"] --> A["30"]
A --> B["20"]
B --> C["10"]
C --> Bottom["Bottom"]

So when someone says “use a stack,” do not picture a specific memory layout first. Picture the rule: the newest item sits on top, and only the top is easy to touch.

Push and pop in action

Let us walk through a concrete sequence. Start with an empty stack.

1. push(10) → stack becomes [10]
2. push(20) → stack becomes [10, 20]
3. push(30) → stack becomes [10, 20, 30]
4. pop() returns 30 → stack becomes [10, 20]
5. push(40) → stack becomes [10, 20, 40]
6. pop() returns 40 → stack becomes [10, 20]

Two things are worth noticing.

First, the stack does not care which value is numerically largest or smallest. 40 comes out before 20 not because 40 > 20, but because 40 was pushed later.

Second, stacks are great whenever “most recent” is the thing you care about. That is why undo history fits naturally. The most recent action is the first one you want to reverse.

If you want a quick mnemonic, imagine the top as the only door into a room. Every new item enters through that door, and every item that leaves must leave through that same door. If 10 went in first and 30 went in last, then 30 is standing closest to the exit. It has to come out first. That is LIFO in one sentence.

Array-backed implementation

The easiest stack implementation in Python uses a plain list, which is really a dynamic array underneath.

• push(x) → append(x)
• pop() → pop()
• peek() → stack[-1]

This works because Python list append and pop-at-the-end are amortized O(1). The top of the stack lives at the end of the array, which is exactly where dynamic arrays are strongest.

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

    def push(self, value):
        self.items.append(value)

    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 from empty stack")
        return self.items[-1]

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

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

import java.util.ArrayList;

class Stack {
    private final ArrayList<Integer> items = new ArrayList<>();

    public void push(int value) {
        items.add(value);
    }

    public int pop() {
        if (isEmpty()) throw new IllegalStateException("empty stack");
        return items.remove(items.size() - 1);
    }

    public int peek() {
        if (isEmpty()) throw new IllegalStateException("empty stack");
        return items.get(items.size() - 1);
    }

    public boolean isEmpty() {
        return items.isEmpty();
    }

    public int size() {
        return items.size();
    }
}

If you were implementing this in C or a lower-level Java-style array, you would usually track a top index. Pushing increments top and writes a value there; popping reads the value at top and decrements it.

Why is array-backed so popular? It is simple, cache-friendly, and usually the fastest in practice. The small caveat is the same one you learned in the dynamic arrays post: occasional resizing makes append/pop amortized O(1), not worst-case O(1) every single time.

Linked-list-backed implementation

You can also build a stack on top of a singly linked list. The trick is to use the head as the top of the stack.

• Push → insert a new node at the head
• Pop → remove the head node
• Peek → read the head node’s value

Each of those is always O(1), with no amortization story needed.

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

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

    def push(self, value):
        self.head = Node(value, self.head)
        self.count += 1

    def pop(self):
        if self.head is None:
            raise IndexError("pop from empty stack")
        value = self.head.value
        self.head = self.head.next
        self.count -= 1
        return value

    def peek(self):
        if self.head is None:
            raise IndexError("peek from empty stack")
        return self.head.value

class Node {
    int value;
    Node next;

    Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}

class LinkedStack {
    private Node head;
    private int size;

    public void push(int value) {
        head = new Node(value, head);
        size++;
    }

    public int pop() {
        if (head == null) throw new IllegalStateException("empty stack");
        int value = head.value;
        head = head.next;
        size--;
        return value;
    }

    public int peek() {
        if (head == null) throw new IllegalStateException("empty stack");
        return head.value;
    }
}

The tradeoff is memory. Each node stores not just the value, but also a pointer/reference. That pointer overhead adds up. So in practice, arrays are usually the default if you have a reasonable size bound or want better cache behavior. A linked list is more attractive when you want a truly unbounded structure without occasional resize copies.

The call stack

This is where stacks stop being “just an interview topic” and start feeling real.

Every time your program calls a function, it pushes a stack frame onto the call stack. That frame holds the information needed for that function call: local variables, parameters, and where to return afterward. When the function finishes, its frame is popped.

Remember the stack region from the memory post? This is what lives there.

Suppose we call factorial(4).

• factorial(4) is called, so its frame is pushed.
• To compute that, it calls factorial(3), so another frame is pushed on top.
• Then factorial(2).
• Then factorial(1).
• factorial(1) hits the base case and returns 1.
• Now frames start popping in reverse order as results unwind: factorial(2) returns 2, factorial(3) returns 6, factorial(4) returns 24.

Notice the perfect stack behavior. The most recently called function is the one that finishes first. That is exactly LIFO.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(4))  # 24

When people say recursion “uses stack space,” this is what they mean. Each unfinished call is sitting on the call stack waiting for the deeper call to finish.

That also explains stack overflow. If recursion goes too deep — maybe because the input is huge, or worse, because you forgot a base case — the program keeps pushing frames until the stack memory limit is exhausted. Then it crashes with a stack overflow or recursion-depth error.

This is why stack thinking matters in day-to-day programming: the stack is not only something you implement; it is something your language runtime is using for you constantly.

Application: balanced parentheses

The classic stack problem is checking whether brackets are balanced.

Examples:

• ([]{}) → balanced
• ([)] → not balanced
• (() → not balanced
• ()) → not balanced

The algorithm is simple:

1. Scan the string from left to right.
2. If you see an opening bracket like (, [, or {, push it.
3. If you see a closing bracket like ), ], or }, then:
   • if the stack is empty, it is invalid immediately,
   • otherwise pop the top opening bracket and check whether the types match.
4. At the end, the string is balanced only if the stack is empty.

Why does a stack fit so perfectly? Because brackets nest. The most recent opening bracket is the one that must be closed first.

In ([{}]), after reading ( then [ then {, the top of the stack is {. So when you read }, that is exactly the bracket you must match next. A queue would be wrong here because it would try to match the oldest opener first, and nesting does not work that way.

Here is the standard Python solution:

def is_balanced(s):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for ch in s:
        if ch in "([{":
            stack.append(ch)
        else:
            if not stack:
                return False
            top = stack.pop()
            if top != pairs[ch]:
                return False

    return len(stack) == 0

print(is_balanced("([]{})"))  # True
print(is_balanced("([)]"))    # False
print(is_balanced("(()"))     # False
print(is_balanced("())"))     # False

The two big edge cases are worth memorizing:

• Unmatched closing bracket: for example ")" or "())" when the stack is already empty.
• Leftover opening bracket: for example "(()" where the scan ends but the stack is not empty.

Once that logic clicks, lots of parser-like problems start feeling much more manageable.

Application preview: next greater element

Here is a teaser for one of the most important stack patterns.

Given an array like [2, 1, 5, 3, 4], the next greater element for 2 is 5, for 1 is 5, for 5 there is none, for 3 is 4, and for 4 there is none.

The naive approach checks to the right for every element, which is O(n²) in the worst case. But with a monotonic stack, you can solve it in O(n) by keeping only the candidates that still matter.

You do not need the full pattern today. Just remember the feeling: a stack can store unresolved items, and when a bigger value arrives, it resolves some of them all at once.

We will dive deep into this in the monotonic stacks and queues post.

Other stack applications

Stacks show up in more places than beginners expect:

• Undo/redo: usually two stacks — one for undo history, one for redo history.
• Expression evaluation: postfix notation like 2 3 + 4 * is almost made for stacks.
• Depth-first search: recursion uses the call stack, but you can also write iterative DFS with an explicit stack.
• Browser history: the back button acts like stack-like history navigation.
• Syntax parsing: compilers and interpreters use stack ideas constantly when matching nested structure.

The common thread is always the same: you care most about the most recently opened, deferred, or visited thing.

Complexity table

Common mistakes

Practice problems

• Valid Parentheses (#20) - Easy
• Min Stack (#155) - Medium
• Evaluate Reverse Polish Notation (#150) - Medium
• Daily Temperatures (#739) - Medium
• Largest Rectangle in Histogram (#84) - Hard

Key takeaways

1. A stack follows LIFO: last in, first out.
2. The top operations — push, pop, and peek — should be O(1).
3. A stack is an interface/behavior, not one specific memory layout.
4. Array-backed stacks are usually the practical default; linked-list-backed stacks trade memory for strict O(1) growth.
5. The call stack is a real stack your program uses for function calls and recursion.
6. Nested-structure problems like balanced parentheses work naturally with stacks because the newest opener must close first.

What’s next

Next: queues and deques — the FIFO counterpart to stacks, with the circular buffer trick that makes array-based queues efficient.