Queues

AQA 4.2.5 — Queues (FIFO)

Retrieval: the Abstract Data Types lesson defined an ADT by its interface, separate from its implementation. A queue is exactly that: a named ADT with its own fixed interface (enqueue, dequeue, is_empty) and a specific behaviour rule — First-In, First-Out (FIFO): the first item added is the first one removed, like a real queue of people.

Operation	Meaning
`enqueue`	add an item to the back of the queue
`dequeue`	remove and return the item at the front of the queue
`is_empty`	check whether the queue has any items

Implementing a queue in Python

queue = []

def enqueue(job):
    queue.append(job)      # add to the back

def dequeue():
    if queue:
        return queue.pop(0)   # remove from the front
    return "Queue empty"

pop(0) removes the item at index 0 — the front — which is what makes this FIFO rather than LIFO. (A production system handling a huge queue would use collections.deque instead of a plain list, since pop(0) on a very long list is inefficient — a genuine engineering refinement beyond what this course requires, but worth knowing exists.)

Common mistake

Queues and stacks are taught back-to-back precisely because they're easy to mix up. A stack's pop() removes the most recently added item (LIFO); a queue's dequeue() removes the least recently added item (FIFO) — opposite ends, opposite behaviour, despite looking similar in code.

Trace it — a printer queue

enqueue("Report.pdf")
enqueue("Timetable.pdf")
dequeue()
enqueue("Letter.pdf")
dequeue()

Step	Operation	Queue contents after	Returned
1	`enqueue("Report.pdf")`	`[Report.pdf]`	—
2	`enqueue("Timetable.pdf")`	`[Report.pdf, Timetable.pdf]`	—
3	`dequeue()`	`[Timetable.pdf]`	`Report.pdf`
4	`enqueue("Letter.pdf")`	`[Timetable.pdf, Letter.pdf]`	—
5	`dequeue()`	`[Letter.pdf]`	`Timetable.pdf`

Choose and justify

A print queue processes documents in the order they were sent — the first document sent is the first one printed. A supermarket checkout works the same way. Both use a queue, not a stack, precisely because fairness (first come, first served) matters — a stack would print/serve the most recently arrived job first, leaving early arrivals waiting indefinitely if new jobs kept arriving. This is the same "choose deliberately" skill from the Introduction to Data Structures lesson, now applied to a concrete choice between two specific ADTs.

Challenge

Extend the printer queue simulation so it also supports a peek operation that returns the front item without removing it, and demonstrate that calling peek twice in a row returns the same job both times (unlike dequeue).

Looking ahead: the next lesson (Stacks) is a queue's exact opposite — LIFO instead of FIFO — using an almost identical interface to deliberately highlight the contrast.

Learn