Stack Data Structure Explained: Push, Pop and Peek

A stack is the simplest container with a rule: you may only touch one end. New items go on the top, and the only item you can take back is the one that went on last. That rule sounds like a limitation, and it is, but it is also exactly the shape of a surprising number of problems: undo, the function call stack, bracket matching, depth-first search, and evaluating expressions.

The problem it solves

Many tasks need to remember things and then deal with them in reverse order of arrival:

• Undo. The last edit is the first one to reverse.
• Nested structure. The most recently opened bracket, tag or function call is the one that must close first.
• Backtracking. A maze walker or a depth-first search returns to the most recent junction with an unexplored branch.
• Deferred work. In a postfix expression, numbers wait until an operator arrives that needs them.

A stack gives you that order for free. You never search, sort or index; you just push when something starts and pop when the most recent thing ends.

The intuition

A stack has three operations that matter, and all three touch only the top:

• push(x) puts x on top.
• pop() removes the top item and returns it.
• peek() returns the top item without removing it.

Because nothing below the top is ever read or moved, each operation costs the same whether the stack holds three items or three million: O(1). The price is reach. To see the item at the bottom you must pop everything above it, and there is no "search the stack" operation in the contract at all.

In Python the natural stack is a list used from its end. append pushes, pop() with no argument pops, and items[-1] peeks. The end matters: pop(0) and insert(0, x) work on the front of the list, and every other element shifts one place, so a stack built on the wrong end is O(n) per operation. append is amortised O(1): the list occasionally grows its buffer and copies, but that cost is spread across many cheap appends. If that occasional copy matters, a linked stack, where each node points at the node below it, is O(1) every time.

The one failure mode is underflow: popping or peeking an empty stack. Python's list raises IndexError, and a good stack class does the same with a clear message rather than returning None, which a caller could mistake for a stored value.

Watch it run

The animation runs the lesson's code, six operations on one pile. A stack is a pile with one open end, and everything happens at the top. stack.append("a") is the first push, and nothing else in the pile is touched, so it is O(1). Push b: it lands on top of a, which is now buried. Push c: three items, and the size never affected the cost. stack[-1] is a peek, reading c without removing it; the pile is unchanged. stack.pop() takes the newest item, c, the last one in. With c gone, b is exposed: last in, first out. Pop again and b comes back, so the stack hands items back in exactly the reverse of their arrival. One item is left, and to read a you had to clear the two sitting on it. That is the price of a stack.

The code

A small stack class on a list, with underflow made explicit, and the classic stack problem it makes easy: evaluating postfix (reverse Polish) notation, where 3 4 + 2 * means (3 + 4) * 2:

class Stack:
    """A stack on a Python list: the end of the list is the top."""
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)                 # amortised O(1)

    def pop(self):
        if not self._items:
            raise IndexError("pop from an empty stack")
        return self._items.pop()              # O(1): nothing else moves

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

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

s = Stack()
for item in "abc":
    s.push(item)
print(s.peek(), len(s))                       # c 3
print(s.pop(), s.pop(), len(s))               # c b 1
s.pop()
try:
    s.pop()
except IndexError as e:
    print(e)                                  # pop from an empty stack

def trunc_div(a, b):
    """Integer division that rounds toward zero, as most RPN problems specify."""
    q = abs(a) // abs(b)
    return q if (a >= 0) == (b > 0) else -q

OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
       "*": lambda a, b: a * b, "/": trunc_div}

def eval_rpn(tokens):
    """Postfix: operands wait on the stack until an operator needs them."""
    st = Stack()
    for t in tokens:
        if t in OPS:
            b, a = st.pop(), st.pop()         # the right operand comes off first
            st.push(OPS[t](a, b))
        else:
            st.push(int(t))
    result = st.pop()
    if len(st):
        raise ValueError("too many operands")
    return result

print(eval_rpn("3 4 + 2 *".split()))          # 14
print(eval_rpn("5 1 2 + 4 * + 3 -".split()))  # 14
print(eval_rpn("7 -2 /".split()))             # -3
print(7 // -2)                                # -4

The last two lines are the trap in that problem: Python's // rounds toward negative infinity, so 7 // -2 is -4, while the usual specification wants truncation toward zero, -3. The same contract without a list, as a chain of (value, node below) pairs, then a check on 3,000 seeded random cases: postfix results against a recursive evaluation of the same random expression tree, and both stacks against a brute-force list that keeps its top at index 0:

class LinkedStack:
    """The same contract with no list: each node is (value, node below)."""
    def __init__(self):
        self.top, self.size = None, 0

    def push(self, x):
        self.top = (x, self.top)              # new node on top: O(1), never a resize
        self.size += 1

    def pop(self):
        if self.top is None:
            raise IndexError("pop from an empty stack")
        x, self.top = self.top
        self.size -= 1
        return x

import random

def random_expr(rng, depth):
    """A random expression tree, returned as (postfix tokens, exact value)."""
    if depth == 0 or rng.random() < 0.3:
        n = rng.randint(-9, 9)
        return [str(n)], n
    op = rng.choice("+-*/")
    left, a = random_expr(rng, depth - 1)
    right, b = random_expr(rng, depth - 1)
    if op == "/" and b == 0:
        op = "+"
    return left + right + [op], OPS[op](a, b)   # recursion, no stack of ours

rng = random.Random(32)
ok = True
for _ in range(3_000):
    tokens, want = random_expr(rng, rng.randint(0, 6))
    ok &= eval_rpn(tokens) == want
    front, st, ls, got = [], Stack(), LinkedStack(), []
    for _ in range(rng.randint(0, 40)):
        if front and rng.random() < 0.45:
            ref = front.pop(0)                  # brute force: top kept at index 0
            got.append(ref == st.pop() == ls.pop())
        else:
            x = rng.randint(0, 99)
            front.insert(0, x); st.push(x); ls.push(x)
    ok &= all(got) and len(front) == len(st) == ls.size
print(ok)                                       # True

The brute force is correct but slow for exactly the reason in the intuition: every insert(0, x) and pop(0) shifts the whole list.

The complexity

• push, pop, peek: O(1). On a list, push is amortised O(1); on a linked stack it is O(1) every time.
• Postfix evaluation: O(n) time for n tokens, O(n) space in the worst case, when every number arrives before any operator.
• Search or access by position: not part of the contract. Doing it anyway means popping, O(n).
• The Big-O cheat sheet lists these next to queues and deques.

Where it goes wrong

• Using the front of a list. insert(0, x) and pop(0) turn every operation into O(n).
• Popping an empty stack. Check first, or let it raise; never return None as if it were a value.
• Swapping the operands. In postfix, the first pop is the right operand. a - b and b - a differ.
• Floor instead of truncation. // is not the division most problems ask for with negative numbers.
• Forgetting the final check. A valid expression leaves exactly one value; leftovers mean malformed input.

When it shows up in interviews

As a warm-up ("implement a stack", "stack vs queue"), then inside classic problems: valid parentheses, evaluate reverse Polish notation, min stack, a queue built from two stacks, the monotonic stack family, and turning recursion into a loop with your own stack. The counterpart is the queue, which serves the oldest item instead of the newest.

How to say it in an interview

"A stack is last in, first out: push, pop and peek all work on the top only, so each is O(1) and nothing below the top moves. In Python I'd use a list from its end, append and pop, never index zero, which would shift everything. I'd raise on an empty pop rather than return None. For reverse Polish notation I push numbers, and on an operator I pop the right operand first, then the left, apply it and push the result, one pass and O(n) time. I'd truncate division toward zero, because Python's floor division rounds negatives the other way."