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
30
30
20
1
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

Push
Just add on top
Instant \(O(1)\)
Pop
Just remove the top
Instant \(O(1)\)
Peek
Look at top, no removal
Instant \(O(1)\)
Search
Must pop down to find it
Slow \(O(n)\)
Space
One 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?

Continue reading