Core · AlgorithmsLesson 4 of 8Free to read

Stacks and queues · Data Structures and Algorithms

When do you need a stack or a queue?

Why you need it

Undo buttons, the browser's back button, matching brackets in code and the function calls in your program all use a stack. Print jobs, message queues and breadth-first search use a queue. Choosing the right one makes many problems short.

The intuition

Stack: last in, first out (LIFO), like a pile of plates. In Python: a list with append() and pop().
Queue: first in, first out (FIFO), like a line at a shop. In Python: collections.deque with append() and popleft().

Don't use list.pop(0) for a queue: it shifts every other item, O(n) each time. deque.popleft() is O(1).

Definition

Stack

A collection where you add and remove at the same end (the top). Last in, first out.

Queue

A collection where you add at the back and remove from the front. First in, first out.

Examples

Balanced brackets

Try it yourself

Push every opening bracket; each closing bracket must match 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

print(balanced("f(a[1]) {x}"))
print(balanced("f(a[1)]"))

Step by step

L6Opening brackets wait on the stack.
L8The most recent opener must match.
L10Leftover openers mean something was never closed.
L13) meets [ on top: mismatch.False

A queue of jobs

Try it yourself

Jobs are served in arrival order. A job that needs another round goes to the back.

from collections import deque

jobs = deque([("print", 2), ("email", 1), ("backup", 3)])
while jobs:
    name, rounds = jobs.popleft()
    print("run", name)
    if rounds > 1:
        jobs.append((name, rounds - 1))

Step by step

L5Take from the front.
L8Unfinished jobs rejoin at the back.
L6Order: print, email, backup, print, backup, backup.

Common mistakes

pop() on an empty stack

[].pop() raises IndexError. Check if stack first, as balanced() does.

list.pop(0) as a queue

It works, but each call is O(n). With 100,000 items, use deque.

Quick quiz

1. What does this print?

stack = []
for x in [1, 2, 3]:
    stack.append(x)
stack.pop()
stack.append(4)
print(stack.pop(), stack)

A
```
4 [1, 2]
```
B
```
3 [1, 2, 4]
```
C
```
1 [2, 4]
```

Show the answer

Answer: A

Push 1, 2, 3; pop 3; push 4; pop 4 leaves [1, 2].

2. The browser back button returns to the page you visited most recently. Which structure fits?

AStack
BQueue
CSet

Show the answer

Answer: A

The most recent page comes back first: last in, first out.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictUndo
Type exactly what this program prints.
ModifyUse a real queue
serve(n) puts customers 1…n in a line and serves them in order, returning the list. pop(0) makes it O(n²). Switch to collections.deque and popleft().
WriteEvaluate postfix
In postfix notation the operator comes after its numbers: "3 4 + 2 *" means (3 + 4) × 2. Write postfix(expr): split on spaces; push numbers on a stack; for + - *, pop two numbers (the second pop is the left side), push the result. Return the final number as an int.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Stack	栈	Last in, first out.
Queue	队列	First in, first out.
Deque	双端队列	A double-ended queue with O(1) adds and removes at both ends.