Queues from Scratch

IB Syllabus: B4.1.1 (HL) – Explain the properties and purpose of ADTs in programming. Implement a queue as an ADT using linked list nodes.

This page is HL only.

Key Concepts
Worked Examples
Quick Code Check
Trace Exercise
Code Completion
Spot the Bug
Output Prediction
Practice Exercises
1. Core
2. Extension
3. Challenge
Connections

Key Concepts

In Queues you learned to use queues with Java’s LinkedList class acting as a queue. On this page you will build a queue from scratch, understanding how enqueue and dequeue work at the node level.

Queue Operations Recap

A queue follows the FIFO (First In, First Out) principle:

Operation	Description	Time
`enqueue(item)`	Add item to the back	O(1) with tail reference
`dequeue()`	Remove and return item from the front	O(1)
`peek()`	View the front item without removing it	O(1)
`isEmpty()`	Check if the queue has no elements	O(1)
`size()`	Return the number of elements	O(1)

Linked List Implementation Strategy

A queue needs efficient access to both ends: enqueue at the back and dequeue from the front. We maintain two references:

front (head) – where items are dequeued
rear (tail) – where items are enqueued

This gives O(1) for both operations, with no traversal needed.

Stack vs Queue – Implementation Comparison

Feature	LinkedStack	LinkedQueue
References maintained	`top` (head only)	`front` (head) + `rear` (tail)
Add	At the head (push)	At the tail (enqueue)
Remove	From the head (pop)	From the head (dequeue)
Principle	LIFO	FIFO
Node class	Same	Same

Both use the same Node class. The only difference is where new items are added: a stack adds and removes at the same end (head), while a queue adds at one end (tail) and removes from the other (head).

Worked Examples

Example 1: LinkedQueue Implementation

public class LinkedQueue {
    private Node front;   // head -- dequeue from here
    private Node rear;    // tail -- enqueue here
    private int count;

    public LinkedQueue() {
        front = null;
        rear = null;
        count = 0;
    }

    // Enqueue: add to the back (tail)
    public void enqueue(String item) {
        Node newNode = new Node(item);
        if (rear == null) {
            // Empty queue: new node is both front and rear
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;   // link current rear to new node
            rear = newNode;        // update rear to new node
        }
        count++;
    }

    // Dequeue: remove and return from the front (head)
    public String dequeue() {
        if (front == null) {
            System.out.println("Queue is empty");
            return null;
        }
        String data = front.data;
        front = front.next;
        if (front == null) {
            rear = null;   // queue is now empty
        }
        count--;
        return data;
    }

    // Peek: view front without removing
    public String peek() {
        if (front == null) {
            System.out.println("Queue is empty");
            return null;
        }
        return front.data;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public int size() {
        return count;
    }

    public void printQueue() {
        System.out.print("FRONT -> ");
        Node current = front;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null <- REAR");
    }

    public static void main(String[] args) {
        LinkedQueue queue = new LinkedQueue();
        queue.enqueue("Alice");
        queue.enqueue("Ben");
        queue.enqueue("Carlos");

        queue.printQueue();
        System.out.println("Peek: " + queue.peek());
        System.out.println("Size: " + queue.size());

        System.out.println("Dequeue: " + queue.dequeue());
        System.out.println("Dequeue: " + queue.dequeue());
        queue.printQueue();
        System.out.println("Size: " + queue.size());
    }
}

Output:

FRONT -> Alice -> Ben -> Carlos -> null <- REAR
Peek: Alice
Size: 3
Dequeue: Alice
Dequeue: Ben
FRONT -> Carlos -> null <- REAR
Size: 1

Notice the FIFO order: Alice was enqueued first and dequeued first.

Critical edge case in dequeue. When the last item is dequeued, front becomes null. You must also set rear = null – otherwise rear still points to the removed node, and the next enqueue would link to a detached node.

Example 2: Print Queue Simulation

A real-world application: simulating a printer queue where documents are processed in order.

public class PrinterQueue {
    public static void main(String[] args) {
        LinkedQueue printQueue = new LinkedQueue();

        // Documents arrive
        printQueue.enqueue("Report.pdf");
        printQueue.enqueue("Invoice.docx");
        printQueue.enqueue("Photo.png");
        printQueue.enqueue("Slides.pptx");

        System.out.println("Print queue:");
        printQueue.printQueue();

        // Process documents in FIFO order
        while (!printQueue.isEmpty()) {
            String doc = printQueue.dequeue();
            System.out.println("Printing: " + doc);
        }

        System.out.println("Queue empty: " + printQueue.isEmpty());
    }
}

Output:

Print queue:
FRONT -> Report.pdf -> Invoice.docx -> Photo.png -> Slides.pptx -> null <- REAR
Printing: Report.pdf
Printing: Invoice.docx
Printing: Photo.png
Printing: Slides.pptx
Queue empty: true

Example 3: Hot Potato Game (Round-Robin)

A queue can simulate round-robin processing: dequeue the front item, process it, then re-enqueue it at the back.

public static String hotPotato(String[] players, int passes) {
    LinkedQueue circle = new LinkedQueue();
    for (String player : players) {
        circle.enqueue(player);
    }

    while (circle.size() > 1) {
        // Pass the potato
        for (int i = 0; i < passes; i++) {
            circle.enqueue(circle.dequeue());  // move front to back
        }
        String eliminated = circle.dequeue();
        System.out.println(eliminated + " is eliminated");
    }
    return circle.dequeue();  // last player standing
}

// hotPotato(new String[]{"Aiko","Ben","Carlos","Diana","Eve"}, 3)
// Eliminations: Diana, Carlos, Eve, Ben
// Winner: Aiko

Quick Code Check

Q1. How many references does a linked queue maintain?

Q2. Where does enqueue add a new item?

Q3. Why must rear be set to null when the last item is dequeued?

Q4. What is the key structural difference between a linked stack and a linked queue?

Q5. What is the time complexity of enqueue and dequeue in a linked queue?

Trace Exercise

Trace the queue state after each operation.

LinkedQueue q = new LinkedQueue();
q.enqueue("X");
q.enqueue("Y");
q.enqueue("Z");
q.dequeue();
q.enqueue("W");
q.dequeue();

After operation	front (peek)	rear	Queue (front to rear)	size()
enqueue("X")			X	1
enqueue("Y")	X			2
enqueue("Z")	X		X, Y, Z
dequeue() returns X		Z		2
enqueue("W")	Y		Y, Z, W	3
dequeue() returns Y		W

Code Completion

Complete the enqueue method for a linked queue.

Fill in the blanks to add an item to the rear of the queue:

public void enqueue(String item) {
    Node newNode = new Node(item);
    if (rear == null) {
        front = newNode;
         = newNode;
    } else {
        rear. = newNode;
        rear = ;
    }
    count++;
}

Complete the dequeue method.

Fill in the blanks to remove and return the front item:

public String dequeue() {
    if (front == null) {
        return null;
    }
    String data = front.;
    front = front.;
    if (front == null) {
         = null;
    }
    count--;
    return data;
}

Spot the Bug

This queue works for multiple items but breaks after dequeuing the last item and then enqueuing again:

1public String dequeue() { 2 if (front == null) { 3 return null; 4 } 5 String data = front.data; 6 front = front.next; 7 count--; 8 return data; 9}

Pick the correct fix:

This queue always returns the most recently added item when dequeuing (LIFO instead of FIFO):

1public void enqueue(String item) { 2 Node newNode = new Node(item); 3 if (rear != null) { 4 rear.next = newNode; 5 } 6 front = newNode; 7 rear = newNode; 8 count++; 9}

Pick the correct fix for line 6:

Output Prediction

What does this code print?

LinkedQueue q = new LinkedQueue();
q.enqueue("1");
q.enqueue("2");
q.enqueue("3");
System.out.println(q.dequeue());
q.enqueue("4");
System.out.println(q.peek());
System.out.println(q.dequeue());
System.out.println(q.size());

Type the exact output: