Очереди и деки

Список позволяет брать элементы откуда угодно. Но часто порядок обработки важен: заказы обслуживают в порядке поступления, а последнее действие отменяют первым. Для этого есть очереди и стеки.

Очередь

Очередь (Queue) работает по принципу «первым пришёл — первым ушёл», как очередь в магазине. offer() ставит элемент в конец, poll() забирает из начала, а peek() только смотрит на первый элемент:

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

Результат:

заказ 1
заказ 2
[заказ 2, заказ 3]

Лучшая реализация очереди в обычных программах — ArrayDeque.

Обработка до опустошения

Если очередь пуста, poll() возвращает null. На этом строят цикл, который обрабатывает элементы, пока они есть:

void main() {
    Queue<String> printer = new ArrayDeque<>(List.of("отчёт.pdf", "фото.jpg"));
    String job;
    while ((job = printer.poll()) != null) {
        IO.println("Печатаю " + job);
    }
    IO.println("Очередь пуста: " + printer.isEmpty());
}

Результат:

Печатаю отчёт.pdf
Печатаю фото.jpg
Очередь пуста: true

Стек

Стек работает наоборот: «последним пришёл — первым ушёл», как стопка тарелок. В Java стек делают на основе интерфейса Deque — двусторонней очереди. push() кладёт элемент наверх, pop() снимает верхний:

void main() {
    Deque<String> history = new ArrayDeque<>();
    history.push("главная");
    history.push("каталог");
    history.push("товар");
 
    IO.println(history.pop());
    IO.println(history.peek());
}

Результат:

товар
каталог

Так работает кнопка «Назад» в браузере. Старый класс Stack тоже существует, но вместо него рекомендуют ArrayDeque.

Двусторонняя очередь

Дек (Deque, от double-ended queue) позволяет добавлять и забирать элементы с обоих концов. Методы называются по концу: 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);
}

Результат:

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

Очередь с приоритетом

PriorityQueue выдаёт элементы не в порядке добавления, а от меньшего к большему — или в порядке, заданном компаратором. Например, сначала самые срочные задачи:

record Task(String title, int priority) {}
 
void main() {
    Queue<Task> tasks = new PriorityQueue<>(Comparator.comparing(Task::priority));
    tasks.offer(new Task("ответить на письмо", 3));
    tasks.offer(new Task("починить сервер", 1));
    tasks.offer(new Task("обновить документацию", 2));
 
    while (!tasks.isEmpty()) {
        IO.println(tasks.poll().title());
    }
}

Результат:

починить сервер
обновить документацию
ответить на письмо

Частая ошибка

PriorityQueue гарантирует порядок только при извлечении через poll(). Если напечатать очередь целиком или обойти её циклом, элементы окажутся в своём внутреннем порядке, а не отсортированными:

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

Результат:

[1, 3, 8, 5]
1

Первым всегда стоит наименьший элемент, остальные — нет. Чтобы получить все элементы по порядку, забирайте их poll() в цикле.

Спасибо, что читаете!

Очередь

Обработка до опустошения

Стек

Двусторонняя очередь

Очередь с приоритетом

Частая ошибка

Спасибо, что читаете!