Что такое стек и его основные принципы работы

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

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

Как отвечать

Стек это тип данных с доступом к одному концу и правилом «последним пришёл, первым вышел». Контракт из четырёх операций: положить, снять, посмотреть верхний, узнать про пустоту. Каждая работает за O(1), доступа к середине нет вовсе, и в этом ограничении вся польза: код, работающий со стеком, невозможно случайно испортить обращением к произвольному элементу.

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

def balanced(s):
    pairs, stack = {")": "(", "]": "["}, []
    for ch in s:
        if ch in "([":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

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

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

Не описывают поведение на пустом стеке. Снятие с пустого это особая ситуация, и решить её надо в контракте заранее: исключение, признак отсутствия или предусловие на вызывающем. Молчаливый возврат пустого значения потом не отличить от настоящего элемента.

Говорят, что добавление всегда O(1), не уточняя про амортизацию. У реализации на массиве отдельное добавление иногда вызывает расширение и копирование, и для систем с жёсткими требованиями к задержке разовый всплеск важнее среднего.

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