Стек в Java: методы, примеры и лучшие практики

Что такое стек

Стек — это коллекция, которая добавляет и убирает элементы только с одного конца, называемого вершиной. Основная идея: последний добавленный элемент извлекается первым (LIFO — last in, first out). В Java класс java.util.Stack расширяет Vector и наследует многие его методы.

Определение в одну строку: Стек — структура данных LIFO, подходящая для обратной обработки, реализации отмены действий и работы со стеком вызовов.

Основные методы Stack

• push(E item) — добавляет элемент на вершину стека.
• pop() — удаляет и возвращает элемент с вершины стека.
• peek() — возвращает элемент с вершины, не удаляя его.
• empty() — возвращает true, если стек пуст.
• search(Object o) — возвращает позицию элемента относительно вершины (вершина имеет позицию 1), или -1 если не найден.

Кроме того, Stack наследует остальные методы Vector, например indexOf, elementAt, clear и т. п.

Создание стека в Java

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        // create a stack
        Stack Customers = new Stack();
    }
}

Код выше создаёт стек Customers, который хранит строки.

Заполнение стека

// populate a stack
Customers.push("Jane Doe");
Customers.push("John Doe");
Customers.push("Patrick Williams");
Customers.push("Paul Smith");
Customers.push("Erick Rowe");
Customers.push("Ella Jones");
Customers.push("Jessica Brown");

После выполнения последней строки вершина стека — “Jessica Brown”.

Просмотр вершины стека

Метод peek() возвращает элемент на вершине без удаления:

// view object at the top of a stack
System.out.println(Customers.peek());

Вывод в консоль:

Jessica Brown

Просмотр всех элементов стека

Хотя стек ограничивает доступ через вершину, вы всё ещё можете использовать унаследованные методы Vector. Самый простой способ получить представление о содержимом — распечатать сам объект:

// view all elements of a stack
System.out.println(Customers);

Вывод:

[Jane Doe, John Doe, Patrick Williams, Paul Smith, Erick Rowe, Ella Jones, Jessica Brown]

Поиск позиции элемента

• indexOf(Object o) возвращает индекс, начиная с 0.
• search(Object o) возвращает положение относительно вершины (1 — вершина). Оба возвращают -1, если элемент не найден.

Примеры:

System.out.println(Customers.indexOf("Jane Doe"));
System.out.println(Customers.search("Jane Doe"));

Вывод:

0
7

Если элемент отсутствует:

System.out.println(Customers.search("Elsa Doe"));
System.out.println(Customers.indexOf("Elsa Doe"));

Вывод:

-1
-1

Обновление элемента в стеке

Вы можете изменять только вершину напрямую. Чтобы обновить элемент, находящийся ниже вершины, нужно снять все элементы выше него, изменить целевой элемент и вернуть элементы назад.

Пример процедуры (упрощённо):

// update an object
Customers.pop();
Customers.pop();
Customers.push("Ella James");
Customers.push("Jessica Brown");
System.out.println(Customers);

Вывод:

[Jane Doe, John Doe, Patrick Williams, Paul Smith, Erick Rowe, Ella James, Jessica Brown]

Этот подход работает, но для частых обновлений произвольных позиций стек неэффективен.

Удаление одного или всех элементов

• Удалить один элемент можно с помощью pop(). Если нужный элемент не на вершине — снимаем верхние элементы пока не дойдём до него.
• Для удаления всех элементов есть два варианта: повторять pop() в цикле или вызвать clear() (унаследовано от Vector), которое быстрее и проще.

// delete all items in a stack
Customers.clear();
System.out.println(Customers.empty());

Вывод:

true

Практические применения стека

Стек подходит для задач, где порядок обработки должен быть обратным порядку поступления. Типичные сценарии:

• Проверка палиндромов.
• Преобразование десятичного числа в двоичное (побитовая сборка в обратном порядке).
• Функциональность «отменить/вернуть» в редакторах.
• Ходы в играх (откат ходов), например для возврата на предыдущие состояния доски.
• Обход в глубину (DFS) в графах при итеративной реализации.

Когда стек не подходит

Важно: стек слишком ограничен, если нужен быстрый доступ или изменения в середине коллекции. В таких случаях используйте:

• ArrayList — быстрый доступ по индексу.
• LinkedList или Deque — эффективные операции добавления/удаления с обоих концов.
• ArrayDeque — рекомендованный современный вариант для реализации стека.

Альтернативы и лучшие практики

Класс Stack синхронизирован (унаследован от Vector), что делает его менее производительным в однопоточных сценариях. Современная рекомендация — использовать ArrayDeque как стек:

import java.util.ArrayDeque;
import java.util.Deque;

Deque stack = new ArrayDeque<>();
stack.push("first"); // добавляет в вершину
String top = stack.peek();
String popped = stack.pop();

ArrayDeque быстрее и не использует устаревшую реализацию Vector. Если нужен потокобезопасный стек, рассмотрите использование ConcurrentLinkedDeque или обёрток синхронизации.

Временная сложность операций (факты)

• push / pop / peek: O(1) амортизированно.
• indexOf / search / remove произвольного элемента: O(n).
• clear: O(n) (зависит от реализации), но обычно быстрее, чем последовательные pop.

Ментальные модели и эвристики

• Представляйте стек как стопку тарелок: кладёте и снимаете только с верхней тарелки.
• Если задача требует «отката» состояний — подумайте о стеке.
• Если нужно часто обращаться к произвольному элементу — стек не ваш выбор.

Пример: обновление среднего элемента с помощью временного стека

Шаблон: снять элементы во вспомогательный стек до достижения целевого элемента, изменить его, вернуть элементы обратно.

public static  void updateAt(Stack s, int indexFromBottom, E newValue) {
    // indexFromBottom — индекс, как в Vector (0 — самый нижний)
    if (s.isEmpty() || indexFromBottom < 0 || indexFromBottom >= s.size()) return;
    Stack temp = new Stack<>();
    int targetIndexFromTop = s.size() - 1 - indexFromBottom;
    for (int i = 0; i < targetIndexFromTop; i++) {
        temp.push(s.pop());
    }
    // теперь вершина — целевой элемент
    s.pop(); // удалить старое значение
    s.push(newValue); // положить обновлённый элемент
    while (!temp.empty()) {
        s.push(temp.pop());
    }
}

Этот метод корректен, но дорогостоящ по времени при больших стэках.

Решение для многопоточности

• Stack синхронизирован, но это устаревшее решение — блокировка на всем объекте Vector.
• Для конкурентных задач лучше использовать ConcurrentLinkedDeque или синхронизироваться с помощью внешних механизмов только там, где это требуется.

Важно: автоматическое наследование синхронизации у Vector не всегда желаемо — оно может скрывать узкие места в производительности.

Чек-листы по ролям

Разработчик:

• Выбрать ArrayDeque вместо Stack для однопоточных задач.
• Избегать частых обновлений внутренних элементов стека.
• Использовать generics для типобезопасности.

Код-ревьювер:

• Проверить необходимость синхронизации.
• Оценить сложность операций: нет ли O(n) в горячем цикле.
• Предложить более подходящую коллекцию при частых произвольных доступах.

Архитектор:

• Решить требования к потокобезопасности.
• Оценить память при большом объёме данных (Vector увеличивает массив; ArrayDeque тоже ресайзится).

Тесты и критерии приёмки

• Unit: push/pop/peek корректно в пустом и непустом стеке.
• Граничные: поиск несуществующего элемента возвращает -1.
• Производительность: операции push/pop не должны деградировать линейно при типичных объёмах (замеры на целевой нагрузке).

Decision flowchart для выбора реализации

flowchart TD
  A[Нужен стек?] --> B{Требуется потокобезопасность}
  B -- Да --> C{Высокая конкуренция}
  B -- Нет --> D[Использовать ArrayDeque]
  C -- Да --> E[Использовать ConcurrentLinkedDeque или внешнюю синхронизацию]
  C -- Нет --> D

Когда стек не должен использоваться — галерея кейсов

• Частые изменения элементов в середине: используйте ArrayList или LinkedList.
• Требуется случайный доступ по индексу: ArrayList.
• Ограничение памяти и предсказуемое поведение при ресайзе: рассмотрите структуры на примитивных массивах.

Итог

Стек — простая и мощная структура для задач LIFO. В Java класс Stack исторически доступен, но для большинства задач сегодня предпочтительнее ArrayDeque из-за производительности и отсутствия ненужной синхронизации. Используйте стек там, где нужен обратный порядок обработки, и помните про временную сложность при операциях вне вершины.

Важно: оценивайте требования к потокобезопасности и частоте операций — это определит лучшую реализацию.

Ключевые термины:

• LIFO — порядок «последний пришёл — первый вышел».
• Вершина — конец стека, где происходят вставки и удаления.