Queues and deques

A list lets you take elements from anywhere. But the order of processing often matters: orders are served in the order they arrive, and the last action is undone first. Queues and stacks exist for this.

A queue

A queue (Queue) works on the "first in, first out" principle, like a line in a shop. offer() puts an element at the end, poll() takes one from the front, and peek() only looks at the first element:

void main() {
    Queue<String> orders = new ArrayDeque<>();
    orders.offer("order 1");
    orders.offer("order 2");
    orders.offer("order 3");
 
    IO.println(orders.poll());
    IO.println(orders.peek());
    IO.println(orders);
}

Output:

order 1
order 2
[order 2, order 3]

The best queue implementation for everyday programs is ArrayDeque.

Processing until empty

If the queue is empty, poll() returns null. This is the basis for a loop that processes elements while there are any:

void main() {
    Queue<String> printer = new ArrayDeque<>(List.of("report.pdf", "photo.jpg"));
    String job;
    while ((job = printer.poll()) != null) {
        IO.println("Printing " + job);
    }
    IO.println("Queue is empty: " + printer.isEmpty());
}

Output:

Printing report.pdf
Printing photo.jpg
Queue is empty: true

A stack

A stack works the other way round: "last in, first out", like a pile of plates. In Java a stack is built on the Deque interface — a double-ended queue. push() puts an element on top, pop() takes the top one off:

void main() {
    Deque<String> history = new ArrayDeque<>();
    history.push("home");
    history.push("catalog");
    history.push("product");
 
    IO.println(history.pop());
    IO.println(history.peek());
}

Output:

product
catalog

This is how the browser's "Back" button works. The old Stack class also exists, but ArrayDeque is recommended instead.

A double-ended queue

A deque (Deque, short for double-ended queue) lets you add and take elements at both ends. The methods are named after the end: offerFirst(), offerLast(), pollFirst(), pollLast():

void main() {
    Deque<Integer> deque = new ArrayDeque<>();
    deque.offerLast(2);
    deque.offerLast(3);
    deque.offerFirst(1);
    IO.println(deque);
    IO.println(deque.pollLast());
    IO.println(deque);
}

Output:

[1, 2, 3]
3
[1, 2]

A priority queue

PriorityQueue hands out elements not in the order they were added but from smallest to largest — or in the order given by a comparator. For example, the most urgent tasks first:

record Task(String title, int priority) {}
 
void main() {
    Queue<Task> tasks = new PriorityQueue<>(Comparator.comparing(Task::priority));
    tasks.offer(new Task("reply to an email", 3));
    tasks.offer(new Task("fix the server", 1));
    tasks.offer(new Task("update the docs", 2));
 
    while (!tasks.isEmpty()) {
        IO.println(tasks.poll().title());
    }
}

Output:

fix the server
update the docs
reply to an email

Common mistake

PriorityQueue guarantees order only when elements are taken out with poll(). If you print the whole queue or loop over it, the elements appear in their internal order, not sorted:

void main() {
    Queue<Integer> queue = new PriorityQueue<>(List.of(5, 3, 8, 1));
    IO.println(queue);
    IO.println(queue.poll());
}

Output:

[1, 3, 8, 5]
1

The smallest element always comes first, the rest do not. To get all the elements in order, take them out with poll() in a loop.

Thanks for reading!

A queue

Processing until empty

A stack

A double-ended queue

A priority queue

Common mistake

Thanks for reading!