Data Structures · Lesson 4 of 8

Stacks and Queues

LIFO stacks, FIFO queues, and everyday uses (undo, BFS).

• Intermediate
• 13 min read
• 3 objectives

Before this lessonLesson 3: Linked Lists

Stacks and queues are simple structures that restrict where you can add and remove items. That restriction is their strength: it matches many real problems exactly and keeps every operation O(1).

Two ways of waiting in line

A stack is a pile of plates: you add to the top and take from the top, so the last one in is the first one out (LIFO). A queue is a line at a shop: people join at the back and leave from the front, so first in, first out (FIFO). Both restrict how you touch the data, and that restriction is exactly what makes them useful for modelling real processes.

Stack: last in, first out

Think of a stack of plates. You add to the top and take from the top. The two core operations are push and pop, plus peek to look without removing. In Python a plain list works: append is push and pop() is pop.

stack = []
stack.append("a")
stack.append("b")
stack.append("c")
print(stack.pop())    # c
print(stack[-1])      # b (peek)
print(stack)

c
b
['a', 'b']

Where stacks show up: the undo button, browser back history, evaluating expressions, and the call stack that tracks running functions (which is why runaway recursion causes a "stack overflow").

Queue: first in, first out

A queue is a line at a shop. You join at the back (enqueue) and are served from the front (dequeue). Do not use list.pop(0) for this: it is O(n). Use collections.deque, which is O(1) at both ends.

from collections import deque

queue = deque()
queue.append("first")
queue.append("second")
queue.append("third")
print(queue.popleft())   # first
print(list(queue))

first
['second', 'third']

Queues run job schedulers, print spoolers, message brokers and breadth-first search.

Worked example: balanced brackets

A stack is the natural tool for checking that every opening bracket has a matching closer in the right order. Push openers; on a closer, the top of the stack must be its partner.

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

print(balanced("{[()]}"))
print(balanced("([)]"))

True
False

Related structures

• Deque: add and remove at both ends.
• Priority queue: serves the smallest (or largest) item first, usually built on a heap (heapq in Python).

A stack in action: undo

history = []

for action in ["type A", "type B", "delete B", "type C"]:
    history.append(action)

print("undo ->", history.pop())
print("undo ->", history.pop())
print("remaining:", history)

undo -> type C
undo -> delete B
remaining: ['type A', 'type B']

A queue in action: first come, first served

Use collections.deque for queues. Removing from the front of a plain list is slow because every item shifts, while deque.popleft() is instant.

from collections import deque

line = deque()
line.append("Ada")
line.append("Linus")
line.append("Grace")

print("serving", line.popleft())
print("serving", line.popleft())
print("waiting:", list(line))

serving Ada
serving Linus
waiting: ['Grace']

Worked example: balanced brackets, explained

Each opening bracket is pushed; each closing bracket must match the most recent unclosed opener, which is exactly the top of the stack.

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

for s in ["([]{})", "([)]", "((", ""]:
    print(repr(s), balanced(s))

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

Where you meet these every day

• The call stack: every function call is pushed, every return pops (this is why infinite recursion crashes with a "stack overflow").
• Browser back button and editor undo: stacks.
• Print spoolers, message brokers, task workers: queues.

Key takeaways

• Stack = LIFO (push and pop at the top); queue = FIFO (enqueue at the back, dequeue at the front).
• Use a list for a stack and collections.deque for a queue.
• Matching-pairs problems (brackets, tags) are a natural fit for a stack.

# Write your solution here