Интерфейс Queue

Queue<E> — коллекция, рассчитанная на обработку элементов в определённом порядке, чаще всего FIFO («первым пришёл — первым вышел»). Расширение Deque<E> — двусторонняя очередь (вставка/удаление с обоих концов), которая также работает как стек.

Основные реализации:

LinkedList — реализует Queue и Deque.
ArrayDeque — массивная двусторонняя очередь, обычно быстрее, чем LinkedList. Рекомендуется как стек и как FIFO-очередь.
PriorityQueue — очередь с приоритетами; элемент с наименьшим значением по Comparable/Comparator выходит первым.
ArrayBlockingQueue, LinkedBlockingQueue (пакет java.util.concurrent) — для многопоточных задач.

Методы Queue

Существуют две формы — бросающая исключение и возвращающая специальное значение:

операция        бросает          возвращает
add(e)          IllegalState     offer(e)  -> boolean
remove()        NoSuchElement    poll()    -> null если пусто
element()       NoSuchElement    peek()    -> null если пусто

Пример 1. ArrayDeque как FIFO-очередь

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

public class QueueFifoDemo {
    public static void main(String[] args) {
        Queue<String> cmds = new ArrayDeque<>();
        cmds.offer("forward");
        cmds.offer("left");
        cmds.offer("stop");

        while (!cmds.isEmpty()) {
            System.out.println("Выполняю: " + cmds.poll());
        }
    }
}

Output:

Выполняю: forward
Выполняю: left
Выполняю: stop

Пример 2. ArrayDeque как стек

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueStackDemo {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Верх: " + stack.peek());
        while (!stack.isEmpty()) {
            System.out.println("pop: " + stack.pop());
        }
    }
}

Output:

Верх: 3
pop: 3
pop: 2
pop: 1

Пример 3. PriorityQueue — задачи по приоритету

import java.util.PriorityQueue;

public class QueuePriorityDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(50);
        pq.offer(10);
        pq.offer(30);
        pq.offer(5);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

Output:

Пример 4. PriorityQueue с Comparator

import java.util.Comparator;
import java.util.PriorityQueue;

public class QueueComparatorDemo {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        PriorityQueue<Task> pq = new PriorityQueue<>(
            Comparator.comparingInt(Task::priority).reversed()
        );
        pq.offer(new Task("blink", 1));
        pq.offer(new Task("emergency-stop", 10));
        pq.offer(new Task("log", 2));

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

Output:

Task[name=emergency-stop, priority=10]
Task[name=log, priority=2]
Task[name=blink, priority=1]

Пример 5. Deque с обоих концов

import java.util.ArrayDeque;
import java.util.Deque;

public class QueueDequeDemo {
    public static void main(String[] args) {
        Deque<String> dq = new ArrayDeque<>();
        dq.offerFirst("A");
        dq.offerLast("B");
        dq.offerFirst("C");
        dq.offerLast("D");

        System.out.println("Deque: " + dq);
        System.out.println("first: " + dq.pollFirst());
        System.out.println("last: " + dq.pollLast());
        System.out.println("Осталось: " + dq);
    }
}

Output:

Deque: [C, A, B, D]
first: C
last: D
Осталось: [A, B]

Подводные камни

add()/remove()/element() бросают исключения на пустой/полной очереди. В обычном коде предпочитайте offer()/poll()/peek().
PriorityQueue не сортирует итерацию: for-each не выдаёт элементы по приоритету. Сортированный порядок получаете только через poll().
PriorityQueue не допускает null.
LinkedList универсален, но медленнее, чем ArrayDeque для роли очереди/стека.
Stack (legacy) использовать не нужно: возьмите ArrayDeque.

См. также

Примечание

Материал подготовлен на основе официального руководства Oracle The Collections Framework и распространяется на условиях Oracle Free Documentation License. Тексты переписаны своими словами, примеры кода — оригинальные.