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 у циклі, як показано в прикладах.