Queue, Deque, Stack: работа с очередями и стеками

1. Интерфейс Queue: классическая очередь (FIFO)

В программировании, как и в жизни, бывают ситуации, когда важно не просто хранить набор элементов, а управлять порядком их обработки. Представьте себе очередь в супермаркете: кто ближе к началу — обслуживается раньше. Это принцип FIFO — «первый пришёл — первый ушёл». А вот стопка тарелок в шкафу работает по принципу LIFO — «последний пришёл — первый ушёл». В Java этим принципам соответствуют коллекции: очереди Queue, двусторонние очереди Deque и стеки Stack.

Где применяются:

• Обработка задач в порядке поступления (очередь задач, печать документов, обработка событий).
• Реализация отмены действий (undo/redo) — стек.
• Парсинг выражений, обход деревьев и графов (поиск в ширину/глубину) и многое другое.

Что такое очередь?

Очередь (Queue) — это коллекция, построенная по принципу FIFO. Элементы добавляются в конец и извлекаются из начала. Как в магазине: кто пришёл раньше, тот обслуживается первым.

Основные методы интерфейса Queue

offer(e)

add(e)

poll()

remove()

peek()

element()

Вы заметили пары методов с похожим поведением. Разница в «мягкости»: offer, poll, peek возвращают специальное значение при неудаче (обычно null или false) и не бросают исключения, а add, remove, element — бросают исключения в граничных ситуациях (пустая очередь, иногда переполнение).

Пример: очередь задач

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> tasks = new LinkedList<>();
        tasks.offer("Почистить зубы");
        tasks.offer("Сделать зарядку");
        tasks.offer("Выпить кофе");

        while (!tasks.isEmpty()) {
            String task = tasks.poll(); // Берём задачу из начала очереди
            System.out.println("Выполняю: " + task);
        }
    }
}

Вывод:

Выполняю: Почистить зубы
Выполняю: Сделать зарядку
Выполняю: Выпить кофе

Почему чаще всего используют LinkedList?

Интерфейс — это контракт, а реализаций несколько. Часто используют LinkedList, поскольку он быстро добавляет/удаляет с обоих концов. Однако отличная альтернатива — ArrayDeque. Есть и специализированные варианты: PriorityQueue (очередь по приоритетам), о ней ниже.

2. Интерфейс Deque: двусторонняя очередь

Deque (Double Ended Queue, «дэк») — очередь, где можно добавлять и удалять элементы с обеих сторон: из начала и из конца. Как автобус с двумя дверями: зайти/выйти можно с любой стороны.

Deque = универсальный солдат: может работать как обычная очередь (FIFO), как стек (LIFO) и как гибрид.

Основные методы интерфейса Deque

addFirst(e)

очередь.addFirst("A")

addLast(e)

очередь.addLast("B")

removeFirst()

очередь.removeFirst()

removeLast()

очередь.removeLast()

peekFirst()

очередь.peekFirst()

peekLast()

очередь.peekLast()

offerFirst(e)

очередь.offerFirst("C")

offerLast(e)

очередь.offerLast("D")

Пример: Deque как очередь и как стек

import java.util.*;

public class DequeDemo {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Используем как очередь (FIFO)
        deque.offerLast("A");
        deque.offerLast("B");
        deque.offerLast("C");
        System.out.println("Очередь (FIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollFirst());
        }

        // Используем как стек (LIFO)
        deque.offerLast("1");
        deque.offerLast("2");
        deque.offerLast("3");
        System.out.println("Стек (LIFO):");
        while (!deque.isEmpty()) {
            System.out.println(deque.pollLast());
        }
    }
}

Вывод:

Очередь (FIFO):
A
B
C
Стек (LIFO):
3
2
1

Почему ArrayDeque?

ArrayDeque — быстрая и компактная реализация Deque на массиве. Для стека и очереди она обычно быстрее и надёжнее, чем старый Stack, и не имеет фиксированного размера (ограничена только памятью).

3. Stack: стек — последний вошёл, первый вышел (LIFO)

Стек — коллекция по принципу LIFO: снимаем верхний элемент последним добавленным. В программировании стек полезен для истории действий (undo), обхода рекурсивных структур (деревья/графы), вычисления выражений и т. п.

Класс Stack (и почему его не стоит использовать)

В Java есть класс Stack, который наследует от устаревшего Vector. Сегодня его не рекомендуют использовать в новых проектах. Предпочтительнее Deque/ArrayDeque.

Методы стека (Deque)

push(e)

pop()

peek()

Внимание: в Deque эти операции соответствуют методам addFirst/removeFirst/peekFirst, но для совместимости есть и «стековые» имена push/pop/peek.

Пример: стек на ArrayDeque

import java.util.*;

public class StackDemo {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("Первый");
        stack.push("Второй");
        stack.push("Третий");

        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}

Вывод:

Третий
Второй
Первый

Почему не Stack?

• Stack синхронизирован (медленнее) и наследует устаревший Vector.
• ArrayDeque чаще быстрее и компактнее, не блокирует потоки.
• Если видите Stack в новом коде — обычно это кандидат на замену ArrayDeque.

4. Когда и что использовать

LinkedList, ArrayDeque, PriorityQueue

ArrayDeque

ArrayDeque, LinkedList

Примеры из жизни:

• Очередь в банке — Queue.
• История действий в редакторе — Stack.
• Очередь автобусов, заезд/выезд с обеих сторон — Deque.

5. Примеры кода: реализуем очередь и стек в мини-приложении

Пример 1: Очередь печати документов

import java.util.*;

public class PrintQueueApp {
    public static void main(String[] args) {
        Queue<String> printQueue = new ArrayDeque<>();
        printQueue.offer("Документ1.pdf");
        printQueue.offer("Документ2.docx");
        printQueue.offer("Документ3.xls");

        while (!printQueue.isEmpty()) {
            String doc = printQueue.poll();
            System.out.println("Печатается: " + doc);
        }
    }
}

Пример 2: Стек отмены действий (undo)

import java.util.*;

public class UndoStackApp {
    public static void main(String[] args) {
        Deque<String> undoStack = new ArrayDeque<>();
        undoStack.push("Вставка текста");
        undoStack.push("Изменение цвета");
        undoStack.push("Удаление картинки");

        System.out.println("Последнее действие: " + undoStack.peek()); // Удаление картинки

        while (!undoStack.isEmpty()) {
            System.out.println("Отмена: " + undoStack.pop());
        }
    }
}

Пример 3: Двусторонняя очередь

import java.util.*;

public class DequeApp {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");
        deque.addLast("D");

        System.out.println("Извлекаем с начала: " + deque.removeFirst()); // C
        System.out.println("Извлекаем с конца: " + deque.removeLast());   // D
        System.out.println("Осталось: " + deque); // [A, B]
    }
}

6. Особенности реализации и нюансы

• ArrayDeque — самая быстрая и универсальная реализация очереди/стека для большинства задач.
• LinkedList — тоже реализует Deque; может быть полезен, но для коротких очередей обычно медленнее, чем ArrayDeque.
• PriorityQueue — очередь по приоритету: порядок определяется приоритетом (естественным или через Comparator), это не обычная FIFO-очередь.
• Stack — устаревший, синхронизированный; в новых проектах предпочтительнее ArrayDeque.
• Deque удобен тем, что позволяет работать и с началом, и с концом структуры, покрывая сценарии очередей и стеков одной абстракцией.

7. Типичные ошибки при работе с очередями и стеками

Ошибка №1: Использование Stack вместо Deque.
Многие новички видят класс Stack и берут его «по названию». В современных проектах вместо него используют ArrayDeque (или LinkedList) с методами push/pop.

Ошибка №2: Нарушение принципа работы структуры.
Пытаются обращаться к элементам очереди/стека по индексу, например queue.get(0) или stack.get(0). Так нельзя — используйте соответствующие методы очередей и стеков (peek, poll, pop и т. п.).

Ошибка №3: Использование remove()/element()/add() без проверки.
Методы remove, element, add могут бросить исключение при пустой/переполненной структуре. Безопаснее пользоваться «мягкими» offer, poll, peek, которые возвращают специальные значения.

Ошибка №4: Использование ArrayDeque с null-элементами.
ArrayDeque не допускает null. Попытка добавить null приведёт к NullPointerException.

Ошибка №5: Использование PriorityQueue как обычной очереди.
В PriorityQueue порядок определяется приоритетами (естественными или заданными через Comparator). Для строгого FIFO используйте ArrayDeque или LinkedList.

Ошибка №6: Модификация очереди/стека во время перебора через for-each.
Удаление элементов из коллекции во время for-each может привести к ConcurrentModificationException. Для удаления используйте итератор или методы poll/pop в цикле, как показано в примерах.

1

Задача

JAVA 25 SELF, 27 уровень, 2 лекция

Недоступна

Просмотр следующей задачи в системе 💼

Просмотр следующей задачи в системе 💼

Открыть

1

Задача

JAVA 25 SELF, 27 уровень, 2 лекция

Недоступна

Имитация работы принтера и истории действий 🖨️🔄

Имитация работы принтера и истории действий 🖨️🔄

Открыть