Какой алгоритм использует коллекция STACK?csharp-129

1. Базовый принцип работы стека

Коллекция Stack<T> реализует принцип LIFO (Last In, First Out - последним пришел, первым вышел). Основные операции:

  • Push - добавление элемента на вершину стека
  • Pop - извлечение элемента с вершины
  • Peek - просмотр верхнего элемента без извлечения

2. Внутренняя структура данных

2.1. Базовая реализация

В .NET Stack<T> использует массив для хранения элементов и отслеживает вершину стека через индекс:

private T[] _array; // Внутренний массив
private int _size;  // Текущее количество элементов
private int _version; // Для контроля изменений при итерации

2.2. Начальная емкость

  • По умолчанию начальная емкость 0
  • При первом добавлении создается массив на 4 элемента
  • При заполнении массив увеличивается в 2 раза

3. Ключевые алгоритмы

3.1. Алгоритм Push

public void Push(T item)
{
    if (_size == _array.Length)
    {
        Grow(_size + 1); // Увеличение массива
    }

    _array[_size] = item;
    _size++;
    _version++;
}

Метод Grow реализует стратегию увеличения массива:

private void Grow(int capacity)
{
    int newCapacity = _array.Length == 0 ? 4 : _array.Length * 2;
    Array.Resize(ref _array, newCapacity);
}

3.2. Алгоритм Pop

public T Pop()
{
    if (_size == 0)
        throw new InvalidOperationException("Stack empty");

    _version++;
    T item = _array[_size - 1];
    _array[_size - 1] = default!; // Для сборщика мусора
    _size--;
    return item;
}

3.3. Алгоритм Peek

public T Peek()
{
    if (_size == 0)
        throw new InvalidOperationException("Stack empty");

    return _array[_size - 1];
}

4. Оптимизации и особенности

  1. Структурный энумератор:
    • Для foreach используется структура, а не класс
    • Избегает аллокаций в куче
public struct Enumerator : IEnumerator<T>
{
    private readonly Stack<T> _stack;
    private int _index;
    public T Current { get; }

    // Реализация интерфейса IEnumerator
}

  1. Пул массивов в .NET 6+:

    • Для больших стеков используется ArrayPool<T>
    • Снижает нагрузку на GC

  2. Thread Safety:

    • Не потокобезопасна по умолчанию
    • Требуется внешняя синхронизация

5. Альтернативные реализации

5.1. Стек на связном списке

Теоретически возможна реализация через узлы:

private class Node<T>
{
    public T Value;
    public Node<T> Next;
}

private Node<T> _head;

Но в .NET выбрана реализация на массиве как более эффективная по:

  • Локализации данных
  • Скорости доступа
  • Использованию памяти

5.2. ImmutableStack

В System.Collections.Immutable есть версия на связных списках:

public sealed class ImmutableStack<T>
{
    private readonly T _head;
    private readonly ImmutableStack<T> _tail;
}

6. Производительность операций

Операция Сложность Примечания
Push O(1)* *Амортизированная при росте массива
Pop O(1) Прямой доступ по индексу
Peek O(1) Прямой доступ по индексу
Contains O(n) Линейный поиск по массиву

Резюмируем:

Stack<T> в .NET использует массив с динамическим расширением, обеспечивая амортизированную O(1) сложность основных операций. Реализация оптимизирована для производительности через структурные энумераторы и эффективное управление памятью.

Вопросы

Собеседования