Stacks Explained

A stack is a linear data structure that stores items in strict Last-In-First-Out (LIFO) order: the last element you push on is the first one you pop off, like a stack of plates where you can only add or remove from the top. Stacks show up everywhere in real systems — the call stack that tracks your function calls, the undo history in a text editor, the back button in a browser, and the machinery behind parsing balanced brackets and arithmetic expressions. Because every operation only ever touches the top, stacks are simple and extremely fast, and understanding them is a prerequisite for recursion, depth-first search, and many parsing algorithms.

Overview / How it works

Picture a stack of dinner plates. You can only place a new plate on top, and you can only remove the plate that is currently on top — you never reach into the middle of the stack. That is exactly the contract a stack data structure enforces: two core operations, push (add to the top) and pop (remove from the top), plus a couple of helpers: peek (look at the top item without removing it) and is_empty (check whether anything is left).

Python has no dedicated Stack class, and it doesn’t need one — a plain list already behaves like a stack if you always add and remove from the same end. Calling list.append(x) pushes x onto the end, and list.pop() (with no argument) removes and returns the last element. This works because Python lists are backed by dynamic arrays: the interpreter keeps a block of memory somewhat larger than the current contents, so adding or removing the last element usually just writes to (or clears) an existing slot — no other elements need to move. That is why append/pop at the end are O(1) on average (amortized), while adding or removing at the front of a list is O(n): every remaining element has to shift over by one to keep the list contiguous in memory.

For cases where you also need fast operations at the other end of the collection (for example, code that behaves as both a stack and a queue), Python’s collections.deque is the standard-library tool: it’s implemented as a doubly linked list of fixed-size blocks, giving O(1) appends and pops at both ends, not just one.

Time and Space Complexity

All of a stack’s core operations only touch the top element, so they’re all constant time — there is no scanning or shifting involved as long as you push/pop from the correct end.

Operation	Description	Time Complexity	Why
push	Add an item to the top	O(1) amortized	Dynamic array occasionally resizes (copies all elements), but that cost is spread over many pushes
pop	Remove and return the top item	O(1)	Only the last slot is touched, no shifting
peek / top	View the top item without removing it	O(1)	Direct index access, e.g. stack[-1]
is_empty	Check whether the stack has any items	O(1)	Just compares length to zero
Search for an arbitrary value	Find an item anywhere in the stack	O(n)	Not a stack-native operation — you have to scan every element

Space complexity is O(n) for n stored elements, since a stack holds every pushed item until it’s popped. There is no meaningful best/average/worst-case split for push/pop the way there is for, say, hashing or sorting — they are O(1) in every case except the rare resize.

Examples

Example 1: Basic push, pop, and peek

from typing import List


def demo_stack_operations() -> None:
    stack: List[int] = []
    stack.append(10)
    stack.append(20)
    stack.append(30)
    print("Stack after pushes:", stack)

    top = stack[-1]
    print("Peek:", top)

    popped = stack.pop()
    print("Popped:", popped)
    print("Stack after pop:", stack)

    print("Is empty:", len(stack) == 0)


demo_stack_operations()

Output:

Stack after pushes: [10, 20, 30]
Peek: 30
Popped: 30
Stack after pop: [10, 20]
Is empty: False

Each push appends to the right-hand end of the list, so after three pushes the top of the stack is 30 — the last item pushed — which is exactly what stack[-1] and stack.pop() return. After the pop, only [10, 20] remain, and the stack is not empty.

Example 2: Validating balanced parentheses

This is the single most common interview use of a stack: check whether every opening bracket has a matching, correctly-nested closing bracket.

def is_valid_parentheses(expression: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack: list[str] = []

    for char in expression:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack.pop() != pairs[char]:
                return False

    return len(stack) == 0


test_cases = ["(a+b)*[c-d]", "([)]", "{[()()]}", "(("]
for expr in test_cases:
    print(f"{expr!r} -> {is_valid_parentheses(expr)}")

Output:

'(a+b)*[c-d]' -> True
'([)]' -> False
'{[()()]}' -> True
'((' -> False

Every opening bracket is pushed. Every closing bracket must match whatever is currently on top of the stack — if the stack is empty (a closing bracket with nothing open) or the popped bracket doesn’t match, the expression is invalid. "([)]" fails because after pushing ( and [, the ) pops [ instead of (. "((" fails because two brackets are left unclosed at the end.

Example 3: Reversing a string with a stack

from collections import deque


def reverse_string(text: str) -> str:
    stack: deque[str] = deque()
    for char in text:
        stack.append(char)

    reversed_chars = []
    while stack:
        reversed_chars.append(stack.pop())

    return "".join(reversed_chars)


word = "stacks"
print(reverse_string(word))

Output:

skcats

Every character of "stacks" is pushed onto a deque used purely as a stack, giving ['s','t','a','c','k','s'] from bottom to top. Popping repeatedly always removes the most recently pushed character first, so the characters come off in reverse order: s, k, c, a, t, s, which joined together spells "skcats".

How it works step by step

Let’s trace is_valid_parentheses from Example 2 on the input "{[()]}" character by character, watching the stack change:

Char	Type	Action	Stack after
{	opening	push	[‘{‘]
[	opening	push	[‘{‘, ‘[‘]
(	opening	push	[‘{‘, ‘[‘, ‘(‘]
)	closing	pop ‘(‘ , matches	[‘{‘, ‘[‘]
]	closing	pop ‘[‘ , matches	[‘{‘]
}	closing	pop ‘{‘ , matches	[]

Every closing bracket pops the most recently opened, still-unmatched bracket — which is always the correct one to check against, because brackets must close in the reverse order they were opened. That’s precisely LIFO order, which is why a stack (and not, say, a queue) is the right tool. By the end, the stack is empty, so the expression is valid.

Common Mistakes

Mistake 1: Pushing and popping from the wrong end

It’s tempting to use insert(0, x) or pop(0) because index 0 feels like a natural “first” position. But for a stack the top is whichever end you’re consistent about, and popping from the front silently returns the oldest item instead of the most recent one — and costs O(n) because every remaining element has to shift left.

stack = []
stack.append("first")
stack.append("second")
stack.append("third")

top_item = stack.pop(0)
print(top_item)

This prints "first" — the very first item pushed, not the most recent one. The bug is silent: no exception is raised, the code just quietly implements queue (FIFO) behavior while the rest of your program assumes stack (LIFO) behavior, and every call also does unnecessary O(n) shifting. The fix is to always operate on the same end, using the default (no-argument) pop(), which removes from the end in O(1):

stack = []
stack.append("first")
stack.append("second")
stack.append("third")

top_item = stack.pop()
print(top_item)

Output:

third

Mistake 2: Popping or peeking an empty stack

Calling pop() or indexing stack[-1] on an empty list raises IndexError, and it’s easy to forget to guard against this once a stack is drained down to zero items (for example, inside a loop that keeps popping until some condition is met).

stack = []
value = stack.pop()
print(value)

This raises IndexError: pop from empty list and crashes the program. Always check whether the stack has anything in it first — an empty list is falsy in Python, so if stack: / if not stack: is enough, no need to compare len(stack) == 0 explicitly:

from typing import Optional, List


def safe_pop(stack: List[int]) -> Optional[int]:
    if not stack:
        print("Stack is empty, nothing to pop")
        return None
    return stack.pop()


stack: List[int] = []
result = safe_pop(stack)
print(result)

Output:

Stack is empty, nothing to pop
None

Best Practices

• Use a plain list with append()/pop() for a simple LIFO stack — both are O(1) amortized because lists are dynamic arrays that grow at the end.
• Never simulate a stack with insert(0, x) or pop(0) — that treats the front as the top, costs O(n) per call, and quietly turns your “stack” into queue behavior.
• Reach for collections.deque instead of list when you need O(1) operations at both ends, or the same object doubles as a queue elsewhere in your code.
• Always guard pop() and stack[-1] with an emptiness check (if stack:) to avoid an IndexError crashing your program.
• Reach for a stack whenever a problem has a “match the most recently seen unmatched thing” shape: balanced brackets, undo/redo history, depth-first search, and evaluating postfix (Reverse Polish) expressions.
• If you need both indexed random access and stack behavior, a plain list already gives you both — there’s no need for a specialized wrapper class.

Practice Exercises

1. Write evaluate_postfix(tokens: list[str]) -> int that evaluates a Reverse Polish Notation expression using a stack. Push numbers as you see them; when you see an operator, pop the two most recent operands, apply the operator, and push the result back. For ["2", "1", "+", "3", "*"] the expected output is 9.
2. Implement a MinStack class supporting push, pop, top, and get_min, all in O(1) time. Hint: maintain a second stack that tracks the minimum value seen so far alongside each push, so you never have to scan the whole stack to find the minimum.
3. Given a string such as "abccba", use a stack to determine whether it’s a palindrome without using Python’s slice-reversal (text[::-1]). Hint: push every character onto a stack, then pop characters one by one and compare them against the string read from the front.

Summary

• A stack enforces Last-In-First-Out (LIFO) order: push and pop both operate only on the top element.
• In Python, use a list‘s append()/pop() for a simple stack, or collections.deque when you need O(1) operations at both ends.
• push, pop, peek, and is_empty are all O(1) (push is amortized O(1)); overall space is O(n) for n stored elements.
• Never simulate a stack with insert(0, ...)/pop(0) — that’s O(n) and behaves like a queue, not a stack.
• Always guard pop()/peek operations with an emptiness check to avoid a crashing IndexError.
• Stacks are the natural fit for nested or matching problems: balanced brackets, undo history, depth-first search, and expression evaluation.