Справочник · модуль 17 «Финал»

Стек

Стек — список, где добавляют и убирают только с конца. Последний пришёл — первым вышел. В Python для этого хватает append и pop.

Пример

def is_balanced(text):
    stack = []
    for ch in text:
        if ch == "(":
            stack.append(ch)
        elif ch == ")":
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0


print(is_balanced("(())"))
print(is_balanced("(()"))
print(is_balanced("())("))

True
False
False

Учитель в уроке Третий приём: стек. Это список, где добавляют и убирают только с конца: последний пришёл, первым вышел. Как стопка тарелок. Открывающую скобку кладём в стек. На закрывающей убираем одну из стека. Если стек опустел раньше времени или не пуст в конце, скобки неправильные.

Запомнить

Стек — как стопка тарелок. Кладёшь сверху и берёшь сверху.

Тема из урока 17.3 «Задачи с собеседований» курса PythonAZ.

В этом же уроке

• Два указателя
• Частоты