Stacks & Queues4 min read

Stack

A pile of plates — the last one you put on is the first one you take off

push: \(O(1)\)pop: \(O(1)\)peek: \(O(1)\)search: \(O(n)\)space: \(O(n)\)

Think about stacking plates in the kitchen. You put a plate on top. Then another. Then another. When you need a plate, you grab the one on top — not the one at the bottom.

That's a stack. It follows one simple rule: Last In, First Out — or LIFO for short.

Push and Pop

There are only two main moves:

Push — add something on top
Pop — remove the top item

You can also peek — look at the top item without removing it.

Where do stacks appear?

Everywhere! Your browser's back button uses a stack. When you hit Ctrl+Z to undo, that's a stack. In algorithms, Depth-First Search uses a stack to explore paths. Even your code runs on a call stack — every time a function calls another function, it gets pushed on. When it returns, it gets popped off.

◈ Push and pop plates!

← → arrow keys to step · click elements to interact

Stack Operations

stack = []
stack.append(10)   # push 10
stack.append(20)   # push 20
stack.append(30)   # push 30
print(stack[-1])   # peek: 30
print(stack.pop()) # pop:  30
print(stack.pop()) # pop:  20
print(len(stack))  # size: 1

Output

Note: A stack only lets you touch the top — like a Pringles can, you can only reach the chip at the opening.

Why is push and pop \(O(1)\)?

The stack always knows where the top is. Adding or removing from the top requires zero searching — it's one step, always. That's why both operations are instant, no matter how tall the stack gets.

Why is search \(O(n)\)?

If you're looking for a specific value buried somewhere in the stack, you'd have to pop items one by one until you find it. In the worst case, you check every item.

The call stack

When your code runs, each function call is pushed onto a call stack. When the function finishes, it's popped off. If you call functions too deeply without returning, you get a stack overflow — the stack runs out of space!

Complexity

PushJust add on top

Instant\(O(1)\)

PopJust remove the top

Instant\(O(1)\)

PeekLook at top, no removal

Instant\(O(1)\)

SearchMust pop down to find it

Slow\(O(n)\)

SpaceOne slot per item

Grows with n\(O(n)\)

Balanced Parentheses Checker

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in ')]}':
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return len(stack) == 0

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

Output

True
False

Challenge

Quick check

You push 10, then 20, then 30 onto a stack. What does pop() return?

Queue

A line of people waiting — the first one in is the first one served

→

Monotonic Stack

A stack that stays sorted — used to find the next bigger or smaller element fast

→

Depth-First Search

Follow one road as far as it goes before backtracking

→

Error HandlingPython

Catch mistakes before they crash your program

→