На этом шаге мы рассмотрим структуру данных стек и ее реализацию с помощью списков.
Структура данных стек (stack) работает по интуитивно понятному принципу "последним поступил, первым обслуживается" (last in, first out, LIFO). Стек аналогичен стопке документов: новые помещаются сверху старых, и по мере работы с этой стопкой первым обрабатывается самый верхний документ. Стек - по-прежнему одна из базовых структур данных в computer science, используемая при управлении операционными системами в алгоритмах, при синтаксическом разборе и поиске с возвратом.
Списки Python могут вполне интуитивным образом играть роль стеков: при использовании операции append() для добавления элемента в стек, а pop() - для удаления последнего добавленного элемента.
stack = [3] stack.append(42) # [3, 42] stack.pop() # 42 (stack: [3]) stack.pop() # 3 (stack: [])
Благодаря эффективности реализации списков обычно можно обойтись без импорта внешних библиотек стеков.
На следующем шаге мы рассмотрим множество.
