Как работает стек

Что проверяют

Понимаете ли вы стек в двух смыслах: как коллекцию Stack<T> и как стек вызовов потока. Следом обычно спрашивают, правда ли, что значимые типы всегда лежат на стеке, и что будет при бесконечной рекурсии.

Как отвечать

Начните со структуры данных. Стек работает по принципу LIFO: последним положили, первым достали. В .NET это Stack<T> из System.Collections.Generic:

• внутри массив: Push кладёт элемент в конец за амортизированное O(1). При заполнении массив удваивается и копируется, поэтому при известном объёме задайте ёмкость в конструкторе;
• Pop и Peek: O(1), на пустом стеке бросают InvalidOperationException. Без исключения обходятся TryPop(out var x) и TryPeek(out var x);
• перебор: foreach идёт от вершины к дну, в порядке будущих Pop;
• потоки: Stack<T> не потокобезопасен, для конкурентного доступа есть ConcurrentStack<T>.

Типичные задачи: проверка скобок, обратная польская запись, отмена действий, обход дерева в глубину без рекурсии.

Затем стек вызовов. Каждый поток получает свой стек фиксированного размера, по умолчанию около мегабайта на Windows. Вызов метода кладёт кадр с аргументами, локальными переменными и адресом возврата, выход снимает его. Переполнение даёт StackOverflowException, и в .NET его нельзя поймать: процесс завершается. Поэтому глубокую рекурсию по пользовательским данным переписывают на явный Stack<T>.

Где спотыкаются

Говорят, что struct всегда лежит на стеке, а class в куче. Значимый тип живёт там, где его контейнер: поле класса лежит в куче вместе с объектом, а локальная переменная, захваченная лямбдой или нужная после await, переезжает в сгенерированный объект в куче.

Обещают поймать StackOverflowException в catch. Это не сработает, процесс упадёт целиком.

Путают стек с очередью. Для FIFO берут List<T> с RemoveAt(0), а это O(n) на каждое извлечение вместо O(1) у Queue<T>.