Алгоритмы на Python

Структура данных стек (stack) в Python

В этом уроке вы с помощью списка Python реализуете основные операции стека: добавление (push), извлечение (pop) и просмотр вершины (peek).

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Кнопке отмены, кнопке «Назад» в браузере и проверке парных скобок нужно одно и то же: запоминать элементы и первым забирать самый свежий. Стек - структура данных, созданная именно для этого.

Пример из жизни

Стек похож на стопку тарелок в столовой. Новые тарелки кладут сверху и берут тоже сверху. Последняя положенная тарелка используется первой, а вытащить тарелку из середины нельзя.

От стопки тарелок к коду
stack.append("third")🍽️ Положить тарелку сверху
stack.pop()⬆️ Снять верхнюю тарелку
stack[-1]👀 Посмотреть на верхнюю тарелку, не снимая
stack📚 Тарелки, оставшиеся в стопке
Последним пришёл, первым ушёл: доступна только верхушка.
Одним предложением

Стек - коллекция «последним пришёл, первым ушёл» (LIFO): элементы добавляются и удаляются только сверху.

Главное

  1. stack.append(...) кладёт элемент наверх, то есть в конец списка.
  2. stack.pop() удаляет и возвращает верхний элемент, здесь "third".
  3. stack[-1] читает верхний элемент, не удаляя его.
  4. И append, и pop работают с концом списка, поэтому они быстрые.

Когда это нужно?

  • История отмены и повтора действий.
  • Проверка парных скобок и разбор выражений.
  • Поиск в глубину и перебор с возвратом без рекурсии.

Когда это не нужно

  • Элементы должны уходить в порядке прихода: это очередь.
  • Нужны элементы из середины или по позиции: лучше подойдёт обычный список или другая структура.

Как это работает

Делайте push и pop и убедитесь, что последний добавленный элемент всегда выходит первым.

Пример кода

Запустить код →
main.py
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.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

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()

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Далее: Поиск в ширину (BFS) в Python →

Попрактикуйтесь на задаче

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

Все задачи