Queues and deques

A queue is first in, first out, the order for breadth-first search and task scheduling. A deque adds and removes at both ends in O(1), which a plain list cannot do at the front.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain first in, first out and where a queue is the natural order
Use a deque to add and remove at both ends in O(1)
Spot why list.pop(0) makes a loop O(n^2)

In practice

A few lines that show Queues and deques doing its job.

Python

from collections import deque

queue = deque(["a", "b"])
queue.append("c")           # enqueue at the back
first = queue.popleft()     # dequeue from the front, O(1)

window = deque(maxlen=3)
for n in [1, 2, 3, 4]:
    window.append(n)        # keeps only the last 3
print(first, list(window))  # a [2, 3, 4]

The common mistake

Watch for

Using list.pop(0) as a queue. It shifts every remaining element, so a loop of dequeues is O(n^2). deque.popleft() is O(1).

What to know first

Your roadmap puts these before Queues and deques, unless you already know them.

Stack applications

How it stays learned

Once a session shows you understand Queues and deques, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Where it leads

Topics that build on Queues and deques.

Previous in the module← Stack applications

Next in the moduleMonotonic stacks →