Что такое 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 размещает элементы в едином непрерывном циклическом массиве, не создает промежуточных объектов и обновляет указатели через быструю битовую маску за один такт. Это дает выигрыш в скорости в 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 (Очередь).