Java Stack

Стек — это коллекция типа «последним пришёл — первым ушёл»: вы pushаете элемент наверх, а следующий pop возвращает именно то, что вы добавили последним. В Java есть два способа построить стек — устаревший класс java.util.Stack из 1995 года и современная рекомендация: Deque<E> (обычно ArrayDeque). Оба работают, оба реализуют одни и те же концептуальные операции, однако официальный Javadoc класса Stack сам указывает на предпочтительность Deque. В этой главе показано, как выглядит Stack, почему JDK теперь советует другое и как использовать рекомендованную замену.

Для чего нужен стек

Стеки встречаются в любом алгоритме, который по своей природе работает по принципу «последним пришёл — первым ушёл»:

• Истории undo/redo — каждое новое действие помещается в стек; undo извлекает последнее.
• Состояние парсера и интерпретатора — вычисление выражений, проверка парных скобок, стековые фреймы.
• Обход в глубину — следующие узлы помещаются в стек, а для посещения извлекаются из него.
• Переворот последовательностей — поместить все элементы, затем извлечь их.

Набор операций всегда один и тот же: push, pop, peek, isEmpty, size. Пять операций.

Устаревший класс Stack

java.util.Stack<E> расширяет Vector<E>, а значит, наследует всё из предыдущей главы — в том числе synchronized на каждом методе, устаревшие имена методов и неудобный факт: это List. По наследованию Stack является индексируемым списком — можно вызвать stack.get(3), что как раз и является той ошибкой проектирования API, которая мотивирует рекомендацию перейти на Deque.

Stack<String> s = new Stack<>();
s.push("a");
s.push("b");
s.push("c");
System.out.println(s.peek());   // c
System.out.println(s.pop());    // c
System.out.println(s.size());   // 2
System.out.println(s.empty());  // false  (note: empty(), not isEmpty())

Шесть методов, специфичных для Stack:

• E push(E item) — добавить наверх. Возвращает элемент.
• E pop() — удалить и вернуть верхний элемент. Бросает EmptyStackException при пустом стеке.
• E peek() — вернуть верхний элемент без удаления. То же исключение.
• boolean empty() — обратите внимание на написание со строчной буквы, отличное от Collection.isEmpty().
• int search(Object o) — расстояние от вершины по основанию 1, или -1, если элемент отсутствует. Странный выбор — результат означает «сколько раз нужно вызвать pop, чтобы достичь o», что редко бывает нужным.

Всё остальное унаследовано от Vector и List.

Почему Javadoc указывает на Deque

Откройте актуальный Javadoc для Stack в любом современном JDK, и вы найдёте строку:

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Причины совпадают с теми, что были описаны в предыдущей главе о Vector:

• Stack синхронизирован на каждом методе. Вы платите за блокировку даже в однопоточном коде, а гранулярность синхронизации неправильна для любой составной операции.
• Stack является List-ом. Индексный доступ к стеку — это ошибка категории: он позволяет заглядывать в середину, нарушая LIFO-дисциплину, которую класс призван соблюдать.
• Пять нужных операций стека уже есть в Deque (push, pop, peek, isEmpty, size), а ArrayDeque — самая быстрая реализация в JDK.

Коротко: Stack работает, но это дизайн 1995 года, втиснутый в фреймворк 1998 года. Новый код должен использовать Deque.

Рекомендованная замена

Идиома умещается в одну строку:

Deque<String> stack = new ArrayDeque<>();

Затем вызывайте push, pop, peek. Интерфейс Deque определяет их как addFirst, removeFirst, peekFirst под капотом, поэтому вершина стека — это голова дека.

Deque<String> calls = new ArrayDeque<>();
calls.push("main");
calls.push("parseArgs");
calls.push("split");
System.out.println(calls.peek());      // split
System.out.println(calls.pop());       // split
System.out.println(calls);              // [parseArgs, main]

Три важных детали:

1. peek() у Deque возвращает null при пустом деке; peek() у Stack бросает исключение. peekFirst() — та же форма с возвратом null. Если нужно исключение, вызовите getFirst() (или element()).
2. То же разграничение применяется для pop() / removeFirst(): pop() бросает исключение при пустом деке.
3. ArrayDeque не допускает элементов null. Используйте его только для ненулевых значений — что обычно и является случаем для стеков.

Когда Stack допустим в новом коде

Почти никогда, и порог невысок:

• Поддержка старого кода, который уже его использует — не стоит переписывать только ради смены класса.
• Работа с API, которое требует именно Stack — крайне редкий случай. Swing-классы, использующие Vector и им подобные, как правило не требуют Stack.

Во всех остальных случаях объявляйте Deque<E> и создавайте экземпляр ArrayDeque<>.

Разобранный пример: проверка скобок двумя способами

Программа ниже использует и Stack, и Deque<Character> для решения классической задачи о парных скобках. Один и тот же алгоритм, две реализации — прочитайте их рядом, затем посмотрите на вариант с Deque и решите, какой из них вы предпочтёте читать через три месяца.

На что стоит обратить внимание:

• Две функции идентичны, если не считать имени типа и empty() против isEmpty(). Нет алгоритмической причины предпочитать Stack — код читается одинаково.
• Блок «Stack-specific API» внизу — это аргумент против устаревшего класса: empty() — другое имя, нетипичное для остального фреймворка; search() возвращает расстояние с основанием 1 (редкость в Java); а get(0) позволяет обращаться к середине стека — что полностью нивелирует смысл абстракции.

Что дальше

Вы теперь познакомились с тремя основными реализациями List (ArrayList, LinkedList, Vector) и LIFO-специализацией, построенной поверх Vector. Следующие четыре главы охватывают аналогичную историю для коллекций с упорядоченным добавлением и извлечением: интерфейс Queue, PriorityQueue, ArrayDeque и более общий контракт Deque.

Практика