Структура данных стек (stack) в Python
В этом уроке вы с помощью списка Python реализуете основные операции стека: добавление (push), извлечение (pop) и просмотр вершины (peek).
Введение
Какую задачу это решает
Кнопке отмены, кнопке «Назад» в браузере и проверке парных скобок нужно одно и то же: запоминать элементы и первым забирать самый свежий. Стек - структура данных, созданная именно для этого.
Пример из жизни
Стек похож на стопку тарелок в столовой. Новые тарелки кладут сверху и берут тоже сверху. Последняя положенная тарелка используется первой, а вытащить тарелку из середины нельзя.
stack.append("third")🍽️ Положить тарелку сверхуstack.pop()⬆️ Снять верхнюю тарелкуstack[-1]👀 Посмотреть на верхнюю тарелку, не снимаяstack📚 Тарелки, оставшиеся в стопкеСтек - коллекция «последним пришёл, первым ушёл» (LIFO): элементы добавляются и удаляются только сверху.
Главное
stack.append(...)кладёт элемент наверх, то есть в конец списка.stack.pop()удаляет и возвращает верхний элемент, здесь"third".stack[-1]читает верхний элемент, не удаляя его.- И
append, иpopработают с концом списка, поэтому они быстрые.
Когда это нужно?
- История отмены и повтора действий.
- Проверка парных скобок и разбор выражений.
- Поиск в глубину и перебор с возвратом без рекурсии.
Когда это не нужно
- Элементы должны уходить в порядке прихода: это очередь.
- Нужны элементы из середины или по позиции: лучше подойдёт обычный список или другая структура.
Как это работает
Делайте push и pop и убедитесь, что последний добавленный элемент всегда выходит первым.
Пример кода
stack = []
stack.append("first")
stack.append("second")
stack.append("third")
print("popped:", stack.pop())
print("top:", stack[-1])
print("stack:", stack)
Результат выполнения
popped: third
top: second
stack: ['first', 'second']
Разбор кода
Метод append() кладёт элемент на вершину стека, а pop() снимает и возвращает верхний элемент, поэтому "third" выходит первым. Через stack[-1] можно посмотреть вершину, не снимая её. Операции append() и pop() в конце списка в среднем выполняются за O(1).
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
pop из пустого стека
pop() у пустого списка вызывает IndexError.
item = stack.pop()
if stack:
item = stack.pop()
Начало списка в роли верхушки
insert(0, x) и pop(0) сдвигают каждый элемент, и это медленно.
stack.insert(0, item)
stack.pop(0)
stack.append(item)
stack.pop()
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Nearest Smaller Value to the Left For each number, find the closest earlier position containing a strictly smaller number. Средне
- Mini Stack-Language Interpreter Evaluate a small stack language. Сложно