Что такое стек в Python

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

Знаете ли вы, что стек это абстракция, а не класс, и умеете ли подбирать под неё реализацию. В задачах обработки данных вопрос почти всегда ведёт к обходу вложенных структур без рекурсии, поэтому проверяют заодно понимание ограничений стека вызовов.

Как отвечать

Стек работает по правилу «последним пришёл, первым вышел»: кладут и снимают с одного конца. Отдельного типа в Python нет, роль стека играет список.

stack = [root]
while stack:
    node = stack.pop()          # снимаем с конца, это O(1)
    for child in node.children:
        stack.append(child)

Список подходит, потому что append и pop без аргумента работают за амортизированное O(1). Писать ради этого класс-обёртку не нужно. Если операции идут с обоих концов, берут collections.deque, если стек делят потоки, берут queue.LifoQueue с блокировками внутри.

Для работы с данными добавьте практическую часть. Рекурсивный обход глубокой вложенности упирается в лимит глубины интерпретатора и падает, потому что хвостовая рекурсия здесь не оптимизируется. Итеративный вариант со своим стеком снимает ограничение и заодно показывает размер оставшейся работы. Отдельно разведите омоним: метод stack у таблицы в pandas переносит уровни колонок в индекс и к структуре данных отношения не имеет.

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

Снимают элемент из начала списка через pop(0). Это O(n), потому что сдвигается весь хвост, и на большом объёме обход из линейного становится квадратичным. Стек должен работать с концом списка.

Считают список потокобезопасным, раз отдельные операции атомарны. Проверить пустоту и тут же снять элемент это два действия, между ними чужой поток успевает опустошить стек, и вызов падает по выходу за границы.

Путают порядок обхода. Стек разворачивает соседей: дети попадают в обработку в обратном порядке добавления. Если порядок важен, их добавляют развёрнутыми или берут очередь, иначе результат окажется верным по составу и неверным по последовательности.