Що таке Stack

Стек працює за принципом стопки чистих тарілок: ви можете покласти нову тарілку лише на самий верх стопки та зняти можете лише верхню тарілку.

🟢 Junior Level

Stack (стек) — це абстрактний тип даних, що являє собою впорядковану колекцію елементів, яка функціонує за принципом LIFO (Last-In, First-Out — «останнім прийшов, першим пішов»).

Базова аналогія

Основні операції стека

push(e): покласти елемент на вершину стека;
pop(): зняти та повернути елемент із вершини стека;
peek(): прочитати верхній елемент без його видалення;
isEmpty(): перевірити, чи порожній стек.

// ❌ АНТИПАТЕРН: Використання застарілого класу java.util.Stack
Stack<String> stack = new Stack<>();

// ✅ СУЧАСНИЙ СТАНДАРТ: ArrayDeque через інтерфейс Deque
Deque<String> stack = new ArrayDeque<>();
stack.push("Перший");
stack.push("Другий");

System.out.println(stack.peek()); // "Другий" (перегляд вершини)
System.out.println(stack.pop());  // "Другий" (вилучення)
System.out.println(stack.pop());  // "Перший"

🟡 Middle Level

1. Архітектурні дефекти `java.util.Stack`

Клас java.util.Stack з’явився ще в JDK 1.0 і визнаний застарілим архітектурним рішенням через три критичні причини:

// Оголошення у стандартній бібліотеці:
public class Stack<E> extends Vector<E>

Грубе порушення принципу підстановки Лісков (LSP): Успадковуючи клас Vector, стек автоматично отримав усі методи списків із довільним доступом за індексом:
```
Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.add(0, 999);    // Вставка в саме дно стека!
stack.remove(1);      // Видалення із середини стека!
stack.get(0);         // Читання довільного елемента за індексом!
```
Це повністю руйнує фундаментальний контракт LIFO: будь-який розробник може випадково порушити порядок вилучення даних.
Падіння продуктивності через synchronized: Усі методи Stack успадкували синхронізацію монітором від Vector. В однопотоковому коді JVM змушена виконувати холості операції захоплення та звільнення монітора на кожен push/pop.
Історичні дивацтва API: Метод stack.search(Object o) повертає позицію елемента, рахуючи з 1 від вершини стека вниз (а не індекс масиву з 0), що регулярно призводить до помилок на одиницю (off-by-one errors).

2. Офіційна альтернатива: `Deque` та `ArrayDeque`

Сама документація JavaDoc класу java.util.Stack містить офіційну рекомендацію творців мови:

«Більш повним та послідовним набором операцій зі стеком LIFO володіє інтерфейс Deque. Переважно слід використовувати реалізацію ArrayDeque: Deque<T> stack = new ArrayDeque<T>();».

Параметр	`java.util.Stack`	`java.util.ArrayDeque`	`java.util.LinkedList`
Базова структура	Динамічний масив `Vector`	Кільцевий циклічний масив	Двозв’язний список вузлів
Складність `push` / `pop`	$O(1)$ аморт.	$O(1)$ аморт.	$O(1)$
Синхронізація	`synchronized` (повільно)	Немає (швидко)	Немає
Доступ за індексом	❌ Можливий (руйнує LIFO)	✅ Заборонений (гарантує LIFO)	✅ Заборонений через інтерфейс `Deque`
Накладні витрати пам’яті	Середні (масив)	Мінімальні	Величезні (вузли `Node`)
Виняток при порожньому `pop()`	`EmptyStackException`	`NoSuchElementException`	`NoSuchElementException`

🔴 Senior Level

1. Як влаштований стек в `ArrayDeque` на бітових масках

ArrayDeque являє собою кільцевий буфер, місткість якого завжди кратна степеню двійки ($2^k$). Це дозволяє замінити повільну операцію взяття остачі від ділення (%) миттєвою побітовою маскою:

// Вставка на вершину стека в ArrayDeque (метод push / addFirst):
public void addFirst(E e) {
    if (e == null) throw new NullPointerException();
    // Зсув покажчика голови назад по кільцю:
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity(); // Ресайз рівно у 2 рази
}

Операція (head - 1) & (elements.length - 1) виконується за 1 машинний такт процесора.
Відсутні виділення проміжних об’єктів у купі, відсутні бар’єри синхронізації, масив неперервний в оперативній пам’яті — процесорний кеш L1 утилізується на 100%.

2. Реалізація конкурентного стека: Стек Трайбера (Treiber Stack)

Якщо стек необхідно використовувати у високонавантаженому багатопотоковому середовищі, використання Collections.synchronizedList() або застарілого Stack призводить до взаємних блокувань і простоїв потоків.

У java.util.concurrent потокобезпечні неблокувальні стеки реалізуються за допомогою алгоритму Трайбера з використанням CAS-операцій (AtomicReference):

public class ConcurrentStack<E> {
    private static class Node<E> {
        final E item;
        Node<E> next;
        Node(E item) { this.item = item; }
    }

    private final AtomicReference<Node<E>> top = new AtomicReference<>();

    public void push(E item) {
        Node<E> newHead = new Node<>(item);
        Node<E> oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead)); // CAS-цикл без блокувань
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = top.get();
            if (oldHead == null) return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }
}

Також на практиці для багатопотокових завдань часто використовують готову неблокувальну структуру ConcurrentLinkedDeque.

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

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

«Стек — це структура даних, що функціонує за принципом LIFO (Last-In, First-Out). У Java стандартний клас java.util.Stack вважається застарілим і непридатним для використання, оскільки він успадковує Vector, порушує принцип підстановки Лісков (LSP) відкриттям методів довільного доступу за індексом і сповільнює код надлишковою синхронізацією кожного методу. Як стек у сучасній Java офіційно рекомендовано використовувати інтерфейс Deque та реалізацію ArrayDeque (Deque<E> stack = new ArrayDeque<>()), що гарантує роботу за константний час $O(1)$ без блокувань та зайвих витрат пам’яті».

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

Чому архітектура class Stack extends Vector порушує принцип підстановки Лісков (LSP)? Відповідь: Принцип LSP стверджує, що підклас повинен розширювати базовий тип без порушення його інваріантів та контрактів. Стек за своїм математичним визначенням зобов’язаний забороняти доступ до будь-яких елементів, крім вершини. Проте успадкування від Vector надало клієнтам стека методи add(int index, E element), get(int index) та remove(int index). Це дозволяє вставляти елементи всередину або діставати їх із самого дна, руйнуючи інваріант LIFO. Стек мав проєктуватися через композицію (внутрішній масив), а не через пряме наслідування від списку.
Чим відрізняється поведінка при вилученні з порожнього стека в java.util.Stack та ArrayDeque? Відповідь: Метод Stack.pop() при спробі вилучення з порожнього стека викидає спеціалізований виняток EmptyStackException. Метод ArrayDeque.pop() (успадкований від інтерфейсу Deque) викидає стандартний виняток NoSuchElementException. При цьому ArrayDeque додатково надає метод pollFirst() (або poll()), який не викидає виняток, а безпечно повертає null на порожній колекції.
Чому ArrayDeque працює швидше за LinkedList у ролі стека? Відповідь: На кожну операцію push у LinkedList алокується новий об’єкт Node у купі, ініціалізуються посилання та створюється сміття для GC, а під час обходу виникають промахи кешу CPU. ArrayDeque розміщує елементи в єдиному неперервному циклічному масиві, взагалі не створює проміжних об’єктів та оновлює індекси через швидку побітову маску за 1 такт. Це забезпечує виграш у швидкодії в 3–5 разів та заощаджує до 80% оперативної пам’яті.
Що таке Стек Трайбера (Treiber Stack) і де він застосовується? Відповідь: Це класичний lock-free алгоритм реалізації потокобезпечного стека на основі однозв’язного списку та атомарної змінної AtomicReference для покажчика вершини стека. Додавання (push) та вилучення (pop) елементів відбуваються у циклі за допомогою операції compareAndSet (CAS). Це дозволяє багатьом потокам паралельно взаємодіяти зі стеком без використання важких блокувань та м’ютексів операційної системи.

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

❌ Використовувати клас java.util.Stack у нових проєктах. (Red Flag: незнання офіційних рекомендацій JavaDoc та застарілості legacy-колекцій).
❌ Стверджувати, що Stack гарантує недоступність елементів за індексом. (Стек успадковує Vector, тому метод get(0) відкритий публічно).
❌ Плутати концепції LIFO (Стек) та FIFO (Черга).