B2.2.4 · Data structures
Queues: first in, first out
A stack always serves the newest arrival first. A queue makes the opposite promise: whoever has been waiting longest is served next, no exceptions.
Explainer
A shared printer in a school computer room prints jobs in exactly the order they were sent. If Ren's essay was sent first, it prints first, even if three other students send jobs a second later. Nobody's job jumps the line, and nobody's job gets stuck behind a job that arrived after it. That ordering guarantee, oldest request served first, is a queue.
A queue keeps items in the exact order they arrived: every new item joins at the rear, and every removal takes whichever item has been waiting at the front the longest. This ordering rule is called First In, First Out (FIFO).
A queue can be built as a static structure using an array (fixed maximum size), or as a dynamic structure with its elements chained together via references (no fixed limit). Same trade-off as B2.2.1 and B2.2.3's stack, just applied to a structure with two ends instead of one. (HL students meet this chained structure by name, as a linked list, when they reach B4.1.3.)
Explainer
The four required operations
The syllabus names these four explicitly, and a queue needs two pointers to support them: a front pointer showing where the next removal comes from, and a rear pointer showing where the next addition goes.
| Operation | What it does | Python (a function per operation) | Java (java.util.Queue) |
|---|---|---|---|
| enqueue | Add a new item at the rear | enqueue(queue, value) | queue.add(value); |
| dequeue | Remove AND return the item at the front | dequeue(queue) | queue.poll(); |
| front | Return the front item WITHOUT removing it | front(queue) | queue.peek(); |
| isEmpty | Check whether the queue has anything in it at all | is_empty(queue) | queue.isEmpty(); |
Java's Queue interface doesn't literally use the words "enqueue" or "dequeue", it names the same four operations add(), poll(), peek() and isEmpty(). The syllabus terms describe the CONCEPT; a real Java program reads these method names instead.
In Python, the cleanest way to teach these four operations is one small function per operation, each taking the queue (a plain list) as its argument:
Every later example on this page calls these four functions instead of writing append/pop(0) directly, so the queue's four required operations stay named exactly as the syllabus states them.
front and dequeue are not the same operation, exactly the same distinction as a stack's peek versus pop. front only reports what's at the front, the queue is unchanged. dequeue genuinely removes it, the queue is one item shorter afterward.
Overflow and underflow apply to queues the same way they apply to stacks. Overflow is attempting to enqueue onto a queue already at its maximum size (a real limit only for a static, array-based queue). Underflow is attempting to dequeue (or check front) on a queue that's already empty. A static implementation commonly adds a fifth operation, isFull, checked BEFORE every enqueue, exactly the "rear pointer has caught up to front" test the circular queue below uses to detect a genuinely full queue.
Explainer
How the choice of implementation affects performance and memory
A queue has one memory problem a stack never faces: as items are removed from the front of a plain array, the freed slots at the start are wasted unless something reclaims them.
A naive array-based queue that always dequeues from index 0 either has to shift every remaining item down one slot (real work, every single dequeue), or simply never reuses the freed space at the front. A circular queue solves this: the rear pointer wraps back around to index 0 once it reaches the end of the array, reusing slots that earlier removals freed. Telling full from empty comes down to comparing the two pointers: they land on the same slot in both cases, so it's genuinely full only right after an addition made them coincide, and genuinely empty only right after a removal did.
Real example: a print queue capped at 10 waiting jobs, the room's shared printer genuinely cannot track an 11th.
Advantage
- Fast enqueue/dequeue (writing to or reading from one known index each time, no shifting needed once it's circular)
Disadvantage
- A genuine maximum size (an 11th job really does trigger overflow, not just a slow enqueue)
Real example: a checkout line with no realistic upper bound on how many shoppers might join it.
Advantage
- No fixed limit (genuinely cannot overflow, grows one linked node at a time as long as memory allows)
Disadvantage
- Extra memory per item (every node stores a link to the next one, on top of the value itself, and allocating that node costs real time on every enqueue)
A plain Python list used as a queue has this exact wasted-work problem in real life: list.pop(0) genuinely has to shift every remaining element down by one, which costs more the longer the queue gets. That's precisely why a real production queue reaches for a circular buffer, or Python's own collections.deque, rather than a plain list.
Worked example
A shared classroom printer queue
Three print jobs, sent in order. The printer only ever looks at whichever job has been waiting longest, exactly the FIFO promise.
Step 1. Three jobs, enqueued in order. Each call to enqueue joins at the rear. Unlike a stack, the queue reads left to right: oldest (front) on the left.
Step 2. front checks what's next, unchanged. The printer can report what it's about to print without touching the queue at all.
Step 3. dequeue actually prints it. "Essay draft" is removed and returned. "Timetable" is now the front, it's been waiting second-longest.
Step 4. isEmpty guards every print request. Before printing again, the printer must check there's actually a job waiting.
Step 5. One more job printed, then genuinely empty. That isEmpty check is exactly what stops the next print request from underflowing.
Try it yourself
Run the print queue
The same enqueue/front/dequeue/isEmpty sequence as the steps above, live and editable, using the same four functions. An experiment is waiting at the bottom: keep dequeuing past the point where the queue is empty, and watch dequeue's pop(0) raise a real error.
Running in offline fallback mode. The full Python engine couldn't load (blocked school network, or no internet), so this console switched automatically to a small hand-written engine. It supports lists used as queues (append, pop(0), indexing, len), exactly what this page needs, but it isn't full Python.
Check your understanding
A queue holds, front to rear: "X", "Y", "Z". front() is called, then dequeue() is called. What does the queue hold afterward, and what did each operation return?
Common mistake
RecurringWhen asked to state an application of a queue, a vague answer like "queues are used for printing" is reported as not specific enough to earn the mark. The mark is for describing the actual mechanism, not just naming a use case in passing.
The second common slip is confusing front with dequeue, treating "check what's next" and "remove what's next" as interchangeable when a question depends on the queue being unchanged afterward.
Answer frame that scores: name the application AND explain the specific enqueue/dequeue mapping. "A printer queue" is not enough; "each print job is enqueued as it's sent, and the printer dequeues and processes whichever job has been waiting longest" is.
What the vague version looks like: "A queue could be used for a printer." Names a use case, explains nothing about how enqueue/dequeue actually implement it.
What it should say: "Each print job is enqueued at the rear as it's sent to the printer. The printer repeatedly dequeues from the front, so the job that has been waiting longest is always printed next, exactly the FIFO order the task requires." States the mechanism, not just the label.
Linking question
How this connects to the rest of the syllabus
The IB syllabus is deliberately woven together, not a stack of isolated topics. Here's how queues (and their sibling structure, the stack) connect specifically to A2 (networks).
Are data structures like stacks and queues applicable in networking algorithms for packet routing and load balancing? (A router genuinely does this: incoming packets are enqueued as they arrive, and the router dequeues and forwards whichever packet has been waiting longest, the exact FIFO order this page's printer queue uses, just with packets instead of print jobs. A round-robin load balancer works the same way, cycling through a queue of servers rather than always sending new traffic to the same one. A stack shows up less directly here, mainly inside the routing software itself, such as tracking a call stack of function calls while a routing decision is being computed, rather than in the packet-handling structure itself.)
Revision questions
Past-paper style. Write an answer, then reveal the marking points and mark yourself.
[2]Distinguish between the front and dequeue operations on a queue.
Marking points
评分要点
- Front returns the item at the front of the queue without removing it, so the queue is unchanged.
- Dequeue removes the item at the front of the queue and returns it, so the queue has one fewer element.
- front 返回队首的项但不移除它,队列保持不变。
- dequeue 移除队首的项并返回它,队列少一个元素。
[3]Explain how a queue could be used to model customers waiting at a checkout.
Marking points
评分要点
- Each arriving customer is enqueued at the back of the queue.
- The cashier serves the customer at the front, who is then dequeued.
- This preserves arrival order: first in, first out, which is fair for a checkout line.
- 每位到达的顾客在队尾入队。
- 收银员服务队首的顾客,该顾客随后出队。
- 这保持了到达顺序:先进先出,对结账队列是公平的。
[4]Explain why a circular queue is more memory-efficient than a simple array-based queue that never reuses freed slots.
Marking points
评分要点
- In a simple array queue the front index advances as items are dequeued, and the space before it is never reused, so the queue reaches the end of the array while slots at the start sit empty.
- A circular queue wraps the rear index back to 0 once it passes the end, filling those freed slots.
- So the circular queue can use the whole array with a fixed amount of memory, instead of needing a larger array or shifting every element forward.
- 在简单数组队列中,队首索引随着出队而前移,它之前的空间从不复用,于是队列到达数组末尾,而开头的位置却空着。
- 环形队列在队尾索引越过末尾后把它绕回 0,填入那些被释放的位置。
- 所以环形队列可以用固定的内存量使用整个数组,而不需要更大的数组或把每个元素前移。
Flashcards
Active recall for this statement’s key terms.
Keep this statement’s practice with you
Free account: unlock every revision question and flashcard for B2.2.4, and every other IB CS 2027 statement.