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

Question

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C# Разработчик

Ответ

Стек (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;
}

Ответ 18+ 🔞

Давай разберём стек, только без этих заумных определений, а как есть. Представь себе стопку тарелок, ну, или, там, блинов — кому что ближе. Берёшь сверху, кладёшь тоже сверху. Последний, который положил, первый и заберёшь. Это и есть стек, ёпта. LIFO — Last In, First Out, или по-нашему: «Кто последний зашёл, тот первый и вышел», как в переполненном лифте.

Что с ним можно делать?

Запихнуть (Push) — сунуть новый элемент наверх стопки.
Выдернуть (Pop) — снять верхний элемент и посмотреть, что это было.
Подсмотреть (Peek/Top) — глянуть на верхний элемент, но не трогать, не разваливать стопку.
Проверить на пустоту (IsEmpty) — понять, не кончилась ли наша стопка тарелок.

В C# это выглядит так: Всё уже придумано до нас, есть готовый класс Stack<T>. Не надо велосипед изобретать, если только тебе не нужно потешить своё ЧСВ.

// Заводим стек, например, для целых чисел
Stack<int> stack = new Stack<int>();

// Запихиваем
stack.Push(10); // Стек: [10]
stack.Push(20); // Стек: [10, 20]
stack.Push(30); // Стек: [10, 20, 30]

// Подсматриваем
int top = stack.Peek(); // top = 30, а стек всё ещё [10, 20, 30]

// Выдёргиваем
int popped = stack.Pop(); // popped = 30, теперь стек [10, 20]

// Не пустой ли?
bool isEmpty = stack.Count == 0; // false, ещё не всё съели

Важные моменты, чтобы не обосраться:

Скорость: Все основные операции (Push, Pop, Peek) — моментальные, O(1). Не зависит от размера стека.
Где применяется: Да везде, блядь! Стек вызовов функций, когда рекурсия уходит вглубь, проверка скобок в выражении, отмена действий (Ctrl+Z), разбор всяких выражений — его хлебом не корми.
Подводные камни в .NET: Если вызвать Pop() или Peek() на пустом стеке, получишь InvalidOperationException прямо в ебальник. Поэтому всегда проверяй stack.Count > 0, прежде чем лезть. Это как перед тем как засунуть руку в банку с печеньем, потрясти её — если не гремит, значит, всё, пиздец, печеньки кончились.

А если очень хочется свою поделку? Ну ладно, вот тебе учебный пример, простой как три копейки. Но в продакшене используй Stack<T>, не выёбывайся.

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; // Пусто или нет
}

Вот и вся магия. Стек — простая, но охуенно полезная штука. Главное — не пытайся достать тарелку из середины стопки, не развалив всё к хуям. Для этого есть другие структуры.