05. Stacks & Queues

LIFO and FIFO are the building blocks for bracket matching, postfix evaluation, and sliding window problems. Learn when to use list and when to switch to deque.

stackqueuedeque

Duration

⏱ ~1 hour

Level

📊 Beginner

Prerequisite

🎯 Lecture 4

OUTCOME

Recognize stack/queue problems and code them in 10 lines.

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

python

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

2. Queue with deque

python

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

⚠️

Never use list.pop(0) for a queue — it's O(n) per call, which silently turns your O(n) algorithm into O(n²).

3. Bracket matching

python

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

python

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

Using list.pop(0) as a queue — O(n) per call. Use deque.popleft().
Popping from an empty stack — always check `if stack:` first.
Confusing operand order in postfix: b is popped before a; the operation is a OP b.
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

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

Example code / lecture materials

All lecture materials and example code are openly available on GitHub.

View on GitHub ↗