Для чего используется структура данных Stack (стек) и каков его принцип работы?

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

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

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

Ключевые сценарии использования:

1. Управление вызовами функций: Стек вызовов (call stack) в runtime языков программирования хранит информацию об активных функциях (точки возврата, локальные переменные).
2. Алгоритмы и парсинг:
   • Проверка корректности вложенных скобок (()()).
   • Вычисление выражений в обратной польской записи (RPN).
   • Обход графов в глубину (DFS).
3. Механизм "Отмена" (Undo): Действия пользователя сохраняются в стек; команда undo извлекает последнее действие.
4. Навигация по истории: Кнопка "Назад" в браузере.

Пример реализации и использования в Java:

// В Java класс java.util.Stack устарел. Рекомендуется использовать Deque.
Deque<Integer> stack = new ArrayDeque<>();

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

// Peek at the top
System.out.println(stack.peek()); // Вывод: 30 (Стек остался: [30, 20, 10])

// Pop elements
System.out.println(stack.pop());  // Вывод: 30 (Стек стал: [20, 10])
System.out.println(stack.pop());  // Вывод: 20 (Стек стал: [10])

// Check if empty
System.out.println(stack.isEmpty()); // Вывод: false

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