📦 Розділ 4 · Питання #9

Що таке Queue і які реалізації існують

У більшості реалізацій черга функціонує за принципом FIFO (First-In, First-Out — «першим прийшов, першим обслужений»), аналогічно до реальної черги покупців перед касою супермар...

📦 Колекції 📄 Вихідний Markdown

🟢 Junior Level

Queue (Черга) — це інтерфейс Java Collections Framework, призначений для утримання елементів у порядку їхньої подальшої обробки.

У більшості реалізацій черга функціонує за принципом FIFO (First-In, First-Out — «першим прийшов, першим обслужений»), аналогічно до реальної черги покупців перед касою супермаркету.

Дві групи методів інтерфейсу Queue

Інтерфейс надає парні методи для кожної операції: одні викидають виняток у разі невдачі, інші повертають спеціальне сигнальне значення (false або null):

Дія з чергою Викидає виняток при помилці Повертає спеціальне значення
Додати в кінець add(e) (викидає IllegalStateException, якщо черга переповнена) offer(e) (повертає false, якщо немає вільного місця)
Вилучити з початку (з видаленням) remove() (викидає NoSuchElementException, якщо черга порожня) poll() (повертає null, якщо черга порожня)
Подивитися початок (без видалення) element() (викидає NoSuchElementException, якщо черга порожня) peek() (повертає null, якщо черга порожня) 
// Приклад стандартного використання черги FIFO
Queue<String> queue = new ArrayDeque<>();

queue.offer("Замовлення #1");
queue.offer("Замовлення #2");

System.out.println(queue.peek()); // "Замовлення #1" (перегляд голови)
System.out.println(queue.poll()); // "Замовлення #1" (вилучення та видалення)
System.out.println(queue.poll()); // "Замовлення #2"
System.out.println(queue.poll()); // null (черга порожня, без винятків)

🟡 Middle Level

1. Основні реалізації у стандартній бібліотеці

У Java не існує єдиного «універсального» класу черги. Конкретна реалізація підбирається під вимоги алгоритму та робоче навантаження:

                          java.util.Queue<E>
                                  │
      ┌───────────────────────────┼───────────────────────────┐
      ▼                           ▼                           ▼
ArrayDeque<E>              PriorityQueue<E>            BlockingQueue<E>
(швидкий кільцевий          (двійкова купа,             (багатопотокові
 масив без блокувань)        сортування за вагою)        блокувальні черги)
  1. ArrayDeque:
    • Високопродуктивний кільцевий динамічний масив.
    • Ідеальний вибір для однопотокового коду (працює швидше за LinkedList у кілька разів).
    • Вставка та вилучення виконуються за строгий константний час $O(1)$.
  2. PriorityQueue:
    • Черга з пріоритетом на базі двійкової купи (Binary Min-Heap) у суцільному масиві.
    • Елементи вилучаються не за черговістю надходження, а за їхнім пріоритетом. За замовчуванням першим вилучається найменший елемент згідно з Comparable або переданим Comparator.
    • Часова складність: offer() — $O(\log N)$, poll() — $O(\log N)$, peek() — $O(1)$.
  3. LinkedList:
    • Реалізує інтерфейс Queue, проте не рекомендується для нових розробок через значний оверхед пам’яті та постійні промахи процесорного кешу.

2. Чому черги забороняють значення null?

Переважна більшість реалізацій Queue (включно з ArrayDeque, PriorityQueue та всіма класами пакета java.util.concurrent) негайно викидають NullPointerException при спробі передати null.

Причина заборони: Методи poll() та peek() використовують значення null як умовний прапорець того, що черга наразі порожня. Якби в чергу дозволялося поміщати null, повернене значення створювало б нерозв’язну невизначеність: чи черга порожня, чи з неї щойно успішно вилучено валідний елемент зі значенням null?

🔴 Senior Level

1. Багатопотокові черги в java.util.concurrent

У паралельному програмуванні черги є архітектурним фундаментом патерну «Виробник — Споживач» (Producer-Consumer):

Клас черги Принцип функціонування Обмеження місткості (Bounded) Механізм синхронізації
ConcurrentLinkedQueue Lock-Free черга на базі CAS Необмежена (Unbounded) Алгоритм Майкла і Скотта (AtomicReference)
ArrayBlockingQueue Блокувальний кільцевий масив Строго обмежена (Bounded) Один спільний ReentrantLock на читання і запис
LinkedBlockingQueue Блокувальний зв’язний список Налаштовувана (за замовчуванням $2^{31}-1$) Два роздільні замки: takeLock та putLock
SynchronousQueue Черга з нульовою місткістю (Rendezvous) Місткість = 0 Потік-виробник безпосередньо чекає потік-споживач
DelayQueue Черга завдань із часовою затримкою Необмежена На базі PriorityQueue + умовні змінні блокувань
LinkedTransferQueue Гібрид LinkedBlockingQueue та SynchronousQueue Необмежена Алгоритм Dual Queue (CAS + паркування потоків)

2. Небезпека необмежених черг (Unbounded Queues) та Backpressure

Одна з найчастіших причин падіння серверних застосунків із помилкою OutOfMemoryError у production — створення пулів потоків із необмеженою чергою завдань:

// ❌ ПРИХОВАНА ЗАГРОЗА OOM:
ExecutorService executor = Executors.newFixedThreadPool(10);
// Під капотом створюється LinkedBlockingQueue з місткістю Integer.MAX_VALUE!

Якщо темп надходження нових завдань (Producer) перевищує швидкість їхньої обробки пулом потоків (Consumer), черга починає неконтрольовано розростатися, накопичуючи мільйони об’єктів у купі, доки JVM не впаде з OutOfMemoryError: Java heap space.

Рішення: Обмежені черги (Bounded Queue) та протитиск (Backpressure)

// ✅ НАДІЙНИЙ PRODUCTION-ПІДХІД:
BlockingQueue<Runnable> queue = new ArrayBlockingQueue<>(1000);
ThreadPoolExecutor pool = new ThreadPoolExecutor(
    4, 8, 60L, TimeUnit.SECONDS, queue,
    new ThreadPoolExecutor.CallerRunsPolicy() // Політика протитиску!
);
  • Коли черга заповнюється до ліміту в 1000 елементів, спрацьовує механізм протитиску (Backpressure).
  • Політика CallerRunsPolicy змушує клієнтський потік, що надіслав завдання, виконувати його самостійно. Це природним чином уповільнює прийом нових запитів ззовні, надійно захищаючи сервіс від вичерпання оперативної пам’яті.

3. Роздільні блокування в LinkedBlockingQueue: Two-Lock Queue

В ArrayBlockingQueue використовується один спільний м’ютекс ReentrantLock. Це означає, що операції запису put() та зчитування take() не можуть виконуватися одночасно: продюсер блокує споживача.

У LinkedBlockingQueue реалізовано алгоритм із двома незалежними блокуваннями:

  • putLock захищає виключно хвіст черги (вставку);
  • takeLock захищає виключно голову черги (вилучення);
  • Потоки-виробники та потоки-споживачі працюють паралельно, не конкуруючи за один і той самий замок. Це забезпечує відчутно більшу пропускну здатність (throughput) на багатоядерних серверах.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь для співбесіди

«Queue — це інтерфейс для впорядкованої обробки елементів (переважно за принципом FIFO). Його методи розділені на дві групи: ті, що викидають винятки (add, remove, element), та ті, що повертають спеціальні сигнальні значення (offer, poll, peek), яким віддають перевагу в бойовому коді. В однопотокових сценаріях стандартом є ArrayDeque ($O(1)$ без оверхеду пам’яті), а для впорядкування за пріоритетом — PriorityQueue (Min-Heap). У багатопотокових системах застосовують реалізації BlockingQueue, де критично важливо використовувати строго обмежену місткість (Bounded Queue) для забезпечення протитиску (Backpressure) та запобігання OOM».

Питання підвищеної складності з відповідями

  1. Чому в більшості реалізацій Queue заборонено зберігати null? Відповідь: Методи poll() та peek() повертають null як сигнальне значення того, що черга наразі порожня. Якби в чергу дозволялося додавати елемент null, виникла б неоднозначність: чи черга порожня, чи з неї щойно успішно вилучено значення null. Щоб запобігти цій невизначеності та позбавити розробників зайвих перевірок, специфікація вимагає негайно викидати NullPointerException при спробі вставити null.

  2. Як влаштований клас PriorityQueue і який елемент вилучається першим за замовчуванням? Відповідь: PriorityQueue побудований на базі структури даних «двійкова купа» (Binary Heap), розміщеної в суцільному масиві. За замовчуванням PriorityQueue є мінімальною купою (Min-Heap), тобто першим завжди вилучається найменший елемент відповідно до природного порядку (Comparable) або переданого компаратора (Comparator). Вставка нового елемента (offer) та вилучення кореня (poll) вимагають $O(\log N)$ операцій просіювання (sift-up / sift-down), а перегляд вершини (peek) виконується за $O(1)$.

  3. У чому полягає принципова різниця в синхронізації між ArrayBlockingQueue та LinkedBlockingQueue? Відповідь: ArrayBlockingQueue використовує єдиний спільний замок ReentrantLock для всіх операцій. Через це операції додавання (put) та вилучення (take) конкурують за один м’ютекс і не можуть відбуватися паралельно. LinkedBlockingQueue використовує два роздільні замки: putLock для хвоста та takeLock для голови. Це дозволяє виробникам і споживачам одночасно маніпулювати чергою без взаємних блокувань.

  4. Що являє собою SynchronousQueue і який її розмір? Відповідь: SynchronousQueue — це спеціалізована блокувальна черга з місткістю, що строго дорівнює нулю. У ній кожен виклик put() блокує потік доти, доки інший потік не викличе take() для безпосередньої передачі цього елемента (механізм рандеву). Виклик size() завжди повертає 0, а ітератор завжди порожній. Вона використовується для синхронного перекидання завдань між потоками, наприклад у пулі Executors.newCachedThreadPool().

Типові помилки та Red Flags

  • ❌ Вважати, що PriorityQueue за замовчуванням вилучає найбільший елемент. (Red Flag: за замовчуванням це Min-Heap, вилучається найменший елемент).
  • ❌ Використовувати Executors.newFixedThreadPool() зі стандартною необмеженою чергою під високим навантаженням. (Прямий ризик падіння програми через OutOfMemoryError).
  • ❌ Намагатися зберегти null в ArrayDeque або BlockingQueue. (Призведе до негайного викидання NullPointerException).

Пов’язані теми