Что такое стек (Stack) в программировании?

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

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

• Push — добавление элемента на вершину стека.
• Pop — извлечение и удаление элемента с вершины.
• Peek/Top — получение элемента с вершины без удаления.
• IsEmpty — проверка на пустоту.

Реализация и пример на C#:

В .NET стек представлен универсальным классом System.Collections.Generic.Stack<T>.

// Создание стека
Stack<int> stack = new Stack<int>();

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

// Peek
int top = stack.Peek(); // top = 30, стек остаётся [10, 20, 30]

// Pop
int popped = stack.Pop(); // popped = 30, стек становится [10, 20]

// Проверка пустоты
bool isEmpty = stack.Count == 0; // false

Ключевые характеристики:

• Сложность операций: O(1) для Push, Pop и Peek.
• Типичное применение:
  • Управление вызовами функций и рекурсией (стек вызовов).
  • Алгоритмы (обход в глубину, проверка сбалансированности скобок).
  • Механизмы отмены действий (Undo).
  • Синтаксический анализ.
• Особенности в .NET: Операции Pop() и Peek() на пустом стеке выбрасывают InvalidOperationException. Рекомендуется всегда проверять stack.Count > 0.

Альтернативная реализация (учебная):

public class SimpleStack<T>
{
    private List<T> _items = new List<T>();

    public void Push(T item) => _items.Add(item);
    public T Pop()
    {
        if (_items.Count == 0) throw new InvalidOperationException("Stack is empty");
        var item = _items[^1]; // Индекс с конца
        _items.RemoveAt(_items.Count - 1);
        return item;
    }
    public T Peek() => _items[^1];
    public bool IsEmpty => _items.Count == 0;
}