05. Stacks & Queues

What you'll learn

• 1Use list as a stack (append/pop)
• 2Use collections.deque as a queue (append/popleft)
• 3Solve bracket matching and postfix-evaluation problems

Overview

Stack = LIFO (Last In First Out). Queue = FIFO (First In First Out). Knowing which one you need is half the battle; the implementation is one method call.

Core Concepts

1. Stack with list

stack = []
stack.append(1)   # push
stack.append(2)
top = stack[-1]   # peek
v = stack.pop()   # pop (LIFO → 2)

2. Queue with deque

from collections import deque
q = deque()
q.append(1)       # enqueue
q.append(2)
v = q.popleft()   # dequeue (FIFO → 1)

3. Bracket matching

def is_valid(s):
    stack = []
    pair = {')': '(', ']': '[', '}': '{'}
    for c in s:
        if c in '([{':
            stack.append(c)
        elif c in ')]}':
            if not stack or stack.pop() != pair[c]:
                return False
    return not stack

4. Postfix evaluation

def eval_postfix(tokens):
    stack = []
    for t in tokens:
        if t.lstrip('-').isdigit():
            stack.append(int(t))
        else:
            b = stack.pop(); a = stack.pop()
            stack.append({'+': a+b, '-': a-b, '*': a*b, '/': a//b}[t])
    return stack[0]

eval_postfix('3 4 + 2 *'.split())   # 14

Examples

Example 1 — src/01_stack_basics.py

Push, pop, peek with a list-as-stack.

Example 2 — src/02_queue_basics.py

Enqueue, dequeue with deque — and the BOJ 'Yosephus' style problems.

Example 3 — src/03_brackets.py

Match three kinds of brackets in one pass.

Example 4 — src/04_postfix.py

Evaluate space-separated postfix expressions.

Common Mistakes

1. Using list.pop(0) as a queue — O(n) per call. Use deque.popleft().
2. Popping from an empty stack — always check `if stack:` first.
3. Confusing operand order in postfix: b is popped before a; the operation is a OP b.
4. Forgetting that integer division in Python is //, not /.

Recap

• Stack with list (append/pop). Queue with deque (append/popleft).
• Bracket matching is the canonical stack problem.
• Postfix evaluation drives much of expression parsing.

Try It

1. BOJ 9012 (Bracket).
2. BOJ 1874 (Stack sequence).