Queues

First in, first out

A queue is the opposite restriction from a stack. You add at the back and remove from the front, so items come out in the order they went in.

The everyday picture is a line of people waiting: you join at the back, and the person at the front is served next.

Java gives you two names for most operations. The offer/poll/peek family returns a signal value when something goes wrong; the add/remove/element family throws. Pick one style and stay with it — mixing them is how you end up with an unexpected exception.

Using one

ArrayDeque again, this time declared as a Queue.

import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> tasks = new ArrayDeque<>();

tasks.offer("calibrate");
tasks.offer("driveForward");
tasks.offer("shoot");

System.out.println(tasks.peek());    // calibrate
System.out.println(tasks.poll());    // calibrate
System.out.println(tasks.poll());    // driveForward
System.out.println(tasks.size());    // 1

Draining a queue completely:

while (!tasks.isEmpty()) {
    String task = tasks.poll();
    System.out.println("running: " + task);
}

Where queues show up

Task scheduling. Actions queued in the order they should run, then drained one per cycle.

class ActionScheduler {
    private final Queue<String> pending = new ArrayDeque<>();

    void schedule(String action) {
        pending.offer(action);
    }

    void runNext() {
        String action = pending.poll();
        if (action != null) {
            System.out.println("executing " + action);
        }
    }

    boolean hasWork() { return !pending.isEmpty(); }
}

Buffering readings. Collect sensor values as they arrive and process them in order.

Breadth-first search. This is the big one. Exploring a grid or graph outward from a starting point, level by level, is a queue at its core — and it is what finds shortest paths in an unweighted graph. See Graphs.

Queue<int[]> frontier = new ArrayDeque<>();
frontier.offer(new int[]{startRow, startCol});

while (!frontier.isEmpty()) {
    int[] cell = frontier.poll();
    // look at each neighbour and offer the unvisited ones
}

Swapping that queue for a stack turns breadth-first search into depth-first search. The structure choice is the algorithm choice, which is a good illustration of why these restrictions matter.

Priority queues

Sometimes arrival order is the wrong order. A PriorityQueue always hands back the smallest element, whatever order things were added.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(50);
pq.offer(10);
pq.offer(30);

System.out.println(pq.poll());   // 10
System.out.println(pq.poll());   // 30
System.out.println(pq.poll());   // 50

For your own types, supply a comparator saying what “smallest” means:

class Task {
    String name;
    int priority;
    Task(String name, int priority) { this.name = name; this.priority = priority; }
}

PriorityQueue<Task> queue =
    new PriorityQueue<>((a, b) -> Integer.compare(a.priority, b.priority));

queue.offer(new Task("shoot", 3));
queue.offer(new Task("stopMotors", 1));
queue.offer(new Task("driveForward", 2));

System.out.println(queue.poll().name);   // stopMotors

Use Integer.compare(a, b) rather than a - b. Subtraction can overflow for large values and give the wrong sign — a bug that only appears on extreme inputs.

For largest-first, reverse the comparison:

new PriorityQueue<>((a, b) -> Integer.compare(b.priority, a.priority));

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(50); pq.offer(10); pq.offer(30);

System.out.println(pq);              // may print [10, 50, 30]
for (int v : pq) System.out.print(v); // NOT in sorted order

Costs

Next