Что такое стек (Stack) как структура данных?

Стек (Stack) — это абстрактный тип данных, работающий по принципу LIFO (Last In, First Out — «последним пришёл, первым ушёл»). Элементы добавляются и удаляются только с одного конца, называемого вершиной (top).

Основные операции:

• push(T item) — добавляет элемент на вершину стека.
• pop() — удаляет и возвращает элемент с вершины стека. Вызывает исключение, если стек пуст.
• peek() — возвращает элемент с вершины стека без его удаления.
• isEmpty() — проверяет, пуст ли стек.

Пример использования java.util.Stack:

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

stack.push(10); // Стек: [10]
stack.push(20); // Стек: [10, 20]
stack.push(30); // Стек: [10, 20, 30]

System.out.println(stack.peek()); // 30 (вершина, стек остаётся [10,20,30])
System.out.println(stack.pop());  // 30 (удалён, стек стал [10,20])
System.out.println(stack.pop());  // 20 (удалён, стек стал [10])

while (!stack.isEmpty()) {
    System.out.println(stack.pop()); // 10
}

Типичные применения стека:

• Управление вызовами функций: стек вызовов (call stack) хранит информацию о активных подпрограммах.
• Алгоритмы: обход графов в глубину (DFS), проверка сбалансированности скобок.
• Вычисление выражений: преобразование и вычисление выражений в обратной польской записи (RPN).
• Механизм отмены (Undo) в приложениях.

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