Stacks, Queues & Deques

We have all seen a pile of plates at home, or a stack of books on a desk.

To add another plate to such a pile, we place it on the top. And to take a plate, we again take it from the top. We do this because in a tall pile it is awkward to slide a plate in or out from the middle or the bottom — the top is the only convenient end. So whatever plate went on last is the first one to come off.

Such an arrangement, where items are added and removed at one end only, is called a stack. The rule it follows has a name worth remembering: LIFO, last in, first out.

Watching a stack work

Let us push a few numbers onto a stack and then take one off, drawing the pile at every step. The little marker shows the top — the only plate we can touch.

Notice the pop step: we pushed 1 then 2, and the very first thing to come back out was 2, the most recent arrival. That is LIFO in one picture.

A queue follows the opposite rule

Now think of the line at a bank counter. The person who arrived first is served first, and newcomers join at the back. Nobody serves the most recent arrival ahead of those who have been waiting.

Such an arrangement, where items are added at one end and removed from the other, is called a queue. Its rule is FIFO, first in, first out — the mirror image of the stack. That single difference, which end you remove from, is the whole distinction. Everything else — the call stack, undo history, breadth-first search, sliding windows — falls out of choosing one rule or the other.

In Python: the right tool for each

For a stack, a plain list is perfect. Adding and removing both happen at the right end, which is the cheap end of a list:

stack = []
stack.append("a")   # push — O(1)
stack.append("b")
print(stack.pop())  # "b" — pop the most recent, O(1)

For a queue, the obvious idea — use a list and remove from the front with pop(0) — hides a nasty cost.

from collections import deque

q = deque()
q.append("a")        # enqueue at the back — O(1)
q.append("b")
print(q.popleft())   # "a" — serve the oldest, O(1)

A deque (double-ended queue) is built for O(1) work at both ends, so it is the honest queue. It is also the natural home for the sliding-window trick: as a window slides across data, you drop stale items from the front and add fresh ones at the back, both in O(1).

A stack in action: balanced brackets

Here is the classic job a stack was born for — checking whether every opening bracket has a matching close, as a code editor does. Each opening bracket gets pushed; each closing bracket must match whatever is on top. If the top does not match, or the stack is empty when a close arrives, the brackets are unbalanced.

def is_balanced(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in s:
        if ch in "([{":
            stack.append(ch)              # opening — remember it
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False              # nothing to match, or wrong match
    return not stack                      # balanced only if nothing is left over

for expr in ["([]{})", "([)]", "(((", "()[]{}"]:
    print(expr, "→", is_balanced(expr))

([]{}) → True
([)] → False
((( → False
()[]{} → True

Look at "([)]". We push (, push [, then meet ) — but the top of the stack is [, not the ( that ) needs, so it is unbalanced. The stack remembers the most recent unclosed bracket, which is exactly the one a closing bracket must answer to. That is LIFO doing useful work.

Where each shows up

• The call stack. Every function call pushes a frame; every return pops one. The most recent call is the one still running — LIFO. (A “stack overflow” is this pile growing too tall.)
• Undo history. Each action is pushed; Ctrl-Z pops the most recent. The last thing you did is the first thing you undo.
• Depth-first vs breadth-first search. A stack explores deep down one path first (DFS); a queue explores level by level (BFS). Same graph, opposite shape, just from the ordering rule.

Practice