Ответ
Стек (stack) — это абстрактная структура данных, работающая по принципу LIFO (Last-In, First-Out, «последним пришел — первым вышел»). Элемент, который был добавлен в стек последним, будет извлечен из него первым.
В Python стек можно реализовать с помощью list, но более эффективным и предпочтительным способом является использование collections.deque.
Почему deque лучше для стека?
Класс deque (двусторонняя очередь) оптимизирован для быстрых операций добавления (append) и удаления (pop) элементов с обоих концов. Эти операции выполняются за константное время O(1). У обычного списка (list) при большом количестве элементов операции могут занимать больше времени из-за особенностей управления памятью.
Основные операции и пример
- Push (добавить элемент):
stack.append(item) - Pop (удалить и вернуть элемент):
stack.pop() - Peek (посмотреть верхний элемент):
stack[-1] - Is Empty (проверить на пустоту):
not stack
from collections import deque
# Создаем стек
stack = deque()
# Добавляем элементы (push)
stack.append('A') # stack: deque(['A'])
stack.append('B') # stack: deque(['A', 'B'])
stack.append('C') # stack: deque(['A', 'B', 'C'])
print(f"Верхний элемент: {stack[-1]}")
# Извлекаем элементы (pop)
top_element = stack.pop()
print(f"Извлечен: {top_element}") # Извлечен: C
print(f"Стек после pop: {stack}") # Стек после pop: deque(['A', 'B'])
# Проверяем, пуст ли стек
if not stack:
print("Стек пуст")Стеки широко применяются для отслеживания вызовов функций (call stack), в алгоритмах обхода графов (DFS), для проверки сбалансированности скобок и реализации функции «Отмена» (Undo).