Stacks and queues

Introduction

A stack and a queue both hold items waiting to be processed. The difference is which item comes out first, and that one rule decides where each is used.

Many problems are really about the order in which waiting work gets done. Choosing between a stack and a queue often is the whole solution, and it explains how your browser's Back button works as well as how a printer manages its jobs.

How it works

A stack: last in, first out

stack = []
stack.append("page 1")
stack.append("page 2")
stack.append("page 3")
top = stack.pop()
print(top, stack)

Think of a pile of plates, or the Back button in a browser. A Python list works as a stack: append puts an item on top, and pop() takes the top item off. Watch the list in the objects panel grow to three cells and then lose the last one: 'page 3' comes out first.

The call stack you have watched in every lesson is exactly this: each call is pushed on top, and the newest call finishes first.

A queue: first in, first out

from collections import deque

queue = deque()
queue.append("Rahim")
queue.append("Nadia")
queue.append("Karim")
served = queue.popleft()
print(served, list(queue))

A queue works like a line at a bank counter: the first person to join is the first one served. Use collections.deque for queues: append joins the back, and popleft() serves the front. (Taking items from the front of a plain list is slow for long lists, because every other item has to move.) Here Rahim joined first, so Rahim is served first.

Syntax

stack = []
stack.append(1)
stack.pop()

from collections import deque
queue = deque()
queue.append(1)
queue.popleft()

Example

def balanced(text):
    stack = []
    pairs = {")": "(", "]": "["}
    for ch in text:
        if ch in "([":
            stack.append(ch)
        elif ch in ")]":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

print(balanced("(a[b])"))
print(balanced("(]"))

Each opening bracket is pushed; each closing bracket must match the one on top of the stack. Step through "(a[b])": ( and [ go on, then ] takes [ off and ) takes ( off, leaving an empty stack, so the text is balanced. For "(]", the ] finds ( on top and the function returns False.

Line by line

1. stack starts empty, and pairs says which opening bracket each closing bracket needs.
2. An opening bracket is pushed onto the stack.
3. A closing bracket must match the top of the stack, or the text is unbalanced.
4. if not stack first deals with a closing bracket that has nothing to match.
5. The result is not stack, so leftover opening brackets count as unbalanced.

Expected result

True
False

In the real world

Text editors use stacks for Undo, and compilers use them to check brackets and evaluate expressions. Queues hold print jobs, messages between services, and customers waiting on a support line.

Common mistakes

• Calling pop() on an empty list raises an IndexError. Check if stack: first.
• Using list.pop(0) for a queue. It works, but it gets slow as the list grows; use deque.popleft().
• Mixing up the ends: pop() takes the newest item, popleft() the oldest.

Best practices

• Pick the structure whose order matches the problem.
• Use deque for queues, because list.pop(0) gets slow.
• Handle the empty case before you remove an item.

Summary

A stack is last in, first out, and a list handles one well. A queue is first in, first out, and deque handles one well. Brackets can be checked by pushing openers and matching closers against the top.

Practice

Extend balanced to handle curly brackets { } as well, and test it with "{[()]}" and "{[(])}".

Mark lesson complete