Стек

Последним пришёл — первым вышел

Стек работает по принципу LIFO (Last In, First Out): последним добавили — первым получили обратно. У него есть одна активная сторона — вершина. Новый элемент кладётся на вершину, и удаляется тоже только вершина.

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

stack.push("A");
stack.push("B");
stack.push("C");

String top = stack.peek(); // C
String removed = stack.pop(); // C

После удаления C вершиной снова становится B. Операции push, peek и pop для ArrayDeque выполняются за O(1) амортизированно.

Стек как память о незавершённом

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

Стек в Java

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