Для чего нужна структура данных стек (Stack) и где она применяется?

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

Базовые операции (на примере System.Collections.Generic.Stack<T> в C#):

var stack = new Stack<string>();

// Push - добавить элемент на вершину стека
stack.Push("First");
stack.Push("Second"); // Вершина стека сейчас -> "Second"

// Peek - посмотреть элемент на вершине БЕЗ удаления
string top = stack.Peek(); // top = "Second", стек остался неизменным

// Pop - извлечь и удалить элемент с вершины
string item = stack.Pop(); // item = "Second", на вершине теперь "First"

// Count - количество элементов
int count = stack.Count; // count = 1

Ключевые области применения:

1. Стек вызовов (Call Stack): Самое важное применение. При вызове метода его контекст (локальные переменные, адрес возврата) "пушится" на стек. При возврате из метода — "попится". Рекурсия полностью основана на этом механизме.
2. Алгоритмы и парсинг:
   • Проверка сбалансированности скобок: (()()) — валидно, (() — нет.

     bool IsBalanced(string expression)
     {
     var stack = new Stack<char>();
     foreach (char ch in expression)
     {
         if (ch == '(') stack.Push(ch);
         else if (ch == ')')
         {
             if (stack.Count == 0) return false; // Закрывающая без открывающей
             stack.Pop();
         }
     }
     return stack.Count == 0; // Все открывающие должны быть закрыты
     }

   • Обратная польская запись (RPN): Алгоритм вычисления выражений типа 3 4 + 5 *.
   • Обход графов в глубину (DFS).
3. Механизм отмены действий (Undo): Каждое действие пользователя (например, в текстовом редакторе) сохраняется в стек. Команда Undo извлекает последнее действие (Pop) и отменяет его.
4. Навигация в UI/Web: История посещений в браузере — это стек (кнопки "Назад"/"Вперед").

Стек vs. Очередь (Queue): Запомните: Стек — LIFO (как стопка тарелок), Очередь — FIFO (как живая очередь).