Queues
IB Syllabus: B2.2.4 – Explain the concept of a queue as a “first in, first out” (FIFO) data structure: enqueue, dequeue, front, isEmpty.
Table of Contents
- Key Concepts
- Using Queues in Java
- Visualising Queue Operations
- Stack vs Queue Comparison
- Real-World Applications
- Worked Examples
- Quick Check
- Trace Exercise
- Code Completion
- Spot the Error
- Predict the Output
- Practice Exercises
- Connections
Key Concepts
What is a Queue?
A queue is an abstract data structure that follows the First In, First Out (FIFO) rule: the first item added is the first item removed. Items are added at the back and removed from the front.
Think of a queue at a ticket counter: the first person in line is the first person served.
Queue Operations
| Operation | Description | Java Method |
|---|---|---|
| Enqueue | Add an item to the back | queue.add(value) |
| Dequeue | Remove and return the front item | queue.poll() |
| Front / Peek | Look at the front item without removing it | queue.peek() |
| isEmpty | Check if the queue has no elements | queue.isEmpty() |
| Size | Get the number of elements | queue.size() |
poll() returns null on an empty queue. remove() throws an exception. Use poll() and check for null, or check isEmpty() first.
Using Queues in Java
import java.util.LinkedList;
import java.util.Queue;
Queue<String> queue = new LinkedList<>();
// Enqueue (add to back)
queue.add("Alice"); // queue: [Alice]
queue.add("Bob"); // queue: [Alice, Bob]
queue.add("Charlie"); // queue: [Alice, Bob, Charlie]
// Peek at the front (does not remove)
System.out.println(queue.peek()); // Alice
// Dequeue (remove from front)
System.out.println(queue.poll()); // Alice queue: [Bob, Charlie]
System.out.println(queue.poll()); // Bob queue: [Charlie]
// Check state
System.out.println(queue.isEmpty()); // false (Charlie is still there)
System.out.println(queue.size()); // 1
Queue is an interface in Java. You create it using LinkedList as the implementation: Queue<Type> q = new LinkedList<>(). This is the standard IB pattern.
Visualising Queue Operations
Enqueue Alice: Enqueue Bob: Enqueue Charlie:
Front → [Alice] Front → [Alice] Front → [Alice]
[Bob] [Bob]
[Charlie] ← Back
Dequeue: Dequeue:
Front → [Bob] Front → [Charlie]
[Charlie]
Items enter at the back and leave from the front. The queue maintains order of arrival.
Stack vs Queue Comparison
| Feature | Stack (LIFO) | Queue (FIFO) |
|---|---|---|
| Access point | Top only | Front (remove) and Back (add) |
| Add operation | Push (to top) | Enqueue (to back) |
| Remove operation | Pop (from top) | Dequeue (from front) |
| Order | Last added = first removed | First added = first removed |
| Analogy | Stack of plates | Queue at a counter |
| Java class | Stack<Type> | Queue<Type> = new LinkedList<>() |
IB exam tip: If the question says “first come, first served” or “order of arrival,” it is a queue. If it says “most recent first” or “undo,” it is a stack.
Real-World Applications
Print Queue
Documents sent to a printer are processed in the order they arrive. The first document sent prints first.
CPU Scheduling
The OS uses queues to manage processes waiting for CPU time. In FCFS (First Come, First Served) scheduling, processes are placed in a queue and executed in arrival order.
Message Queues
Chat applications and notification systems use queues to deliver messages in the order they were sent.
Network Buffers
Routers buffer incoming packets in a queue. Packets are forwarded in the order they arrive to prevent data being sent out of sequence.
When you see FIFO in an exam question, think queue.
Worked Examples
Example 1: Customer Service Simulation
Simulate a ticket counter where customers arrive and are served in order.
import java.util.LinkedList;
import java.util.Queue;
public class TicketCounter {
public static void main(String[] args) {
Queue<String> customers = new LinkedList<>();
// Customers arrive
customers.add("Alice");
customers.add("Bob");
customers.add("Charlie");
customers.add("Diana");
System.out.println("Waiting: " + customers.size()); // 4
// Serve customers in order
while (!customers.isEmpty()) {
String next = customers.poll();
System.out.println("Now serving: " + next);
}
System.out.println("All served: " + customers.isEmpty()); // true
}
}
Output:
Waiting: 4
Now serving: Alice
Now serving: Bob
Now serving: Charlie
Now serving: Diana
All served: true
Example 2: Task Scheduler
Process tasks in arrival order, with the option to add new tasks during processing.
public static void processJobs(Queue<String> jobs) {
while (!jobs.isEmpty()) {
String current = jobs.poll();
System.out.println("Processing: " + current);
// Simulate a task that generates a follow-up
if (current.equals("Print report")) {
jobs.add("Email report"); // new task added to the back
}
}
}
This is a common pattern: processing one item may generate new items that are added to the back of the queue. The new items wait their turn.
Quick Check
Q1. What does FIFO mean?
Q2. You enqueue X, Y, Z (in that order). Then dequeue(), then peek(). What does peek() return?
Q3. Which scenario is best modelled by a queue?
Q4. How do you create a Queue in Java?
Q5. Why would a stack be a poor choice for a print queue?
Trace Exercise
Trace the queue contents after each operation.
Trace: Track the queue contents and return values.
Queue<Integer> q = new LinkedList<>();
q.add(10); // Op 1
q.add(20); // Op 2
q.add(30); // Op 3
q.poll(); // Op 4
q.add(40); // Op 5
q.poll(); // Op 6
q.peek(); // Op 7| After Op | Queue (front to back) | Return Value |
|---|---|---|
| 1 | [10] | -- |
| 2 | [10, 20] | -- |
| 3 | [10, 20, 30] | -- |
| 4 | ||
| 5 | -- | |
| 6 | ||
| 7 |
Code Completion
Complete the method that processes all customers in a queue.
Fill in the blanks: Serve each customer until the queue is empty.
public static void serveAll(Queue<String> customers) {
while (!customers.) {
String next = customers.;
System.out.println("Serving: " + next);
}
}Spot the Error
This code should process items in FIFO order, but it processes them in LIFO order.
Bug Hunt: This code is supposed to process tasks in the order they were added, but the most recently added task runs first.
Pick the correct fix for line 1:
Predict the Output
Predict: What does this code print?
Queue<String> q = new LinkedList<>();
q.add("A");
q.add("B");
q.add("C");
System.out.println(q.poll());
q.add("D");
System.out.println(q.poll());
System.out.println(q.peek());Practice Exercises
Core
-
Queue trace – Starting with an empty queue, perform these operations and write the queue contents after each: enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D), dequeue(), peek(), dequeue().
- Stack or Queue? – For each scenario, state whether a stack or queue is more appropriate and explain why:
- (a) Processing customer orders at a restaurant
- (b) Browser back button history
- (c) CPU scheduling (FCFS)
- (d) Evaluating nested brackets
- Customer service – Write a program that creates a queue of 5 customer names, then processes them one by one, printing “Now serving: [name]” for each.
Extension
-
Priority simulation – Modify the customer service program: regular customers join the back of the queue, but VIP customers join at position 1 (behind whoever is currently being served). Use
add(index, value)from LinkedList for VIP insertion. -
Hot potato – Implement the “hot potato” game: n people stand in a circle (modelled as a queue). Count to k, then remove the person at the front. Continue until one person remains. The removed person goes to the back k-1 times, then is removed on the kth count.
Challenge
- Two-queue stack – Implement a stack using two queues (no actual Stack allowed). You must support push, pop, and peek. Hint: one queue is the “main” storage, the other is used temporarily during push or pop.
Connections
- Prerequisites: ArrayList – dynamic collections and Java generics
- Related: Stacks – LIFO counterpart to queues
- Related: Scheduling – FCFS scheduling uses a queue
- Forward: ADTs: Queues from Scratch (HL) – implementing your own queue