Стек — это одномерная структура данных, напоминающая стопку документов. Особенность стека в том, что доступ к его содержимому возможен только с верхнего документа. Когда появляется новый документ, его размещают на вершине уже существующей стопки.
Это схема стека. Пока в нем только один синий блок — элемент Blue. Чтобы добавить данные, используют команду push. Сначала в стек помещают зеленый блок — элемент Green, затем красный блок — элемент Red.
Извлечение данных из стека (операция pop) начинается с его верхней части. То есть первыми удаляются самые последние добавленные элементы. В нашем случае первым извлекается элемент Red.
Принцип доступа «последним вошёл, первым вышел», когда сначала берут то, что лежит наверху, называется LIFO (Last In, First Out). Стек, как и списки с массивами, представляет собой одномерную структуру. Но, в отличие от них, данные можно добавлять или удалять только с одного конца — вершины стека. Если тебе нужны данные из середины, придётся удалить всё, что находится выше.
Стеки кажутся неудобными из-за ограничения, позволяющего работать только с одного конца. Однако они полезны, когда нужен доступ только к последним данным.
Например, чтобы проверить баланс скобок в строке, будем считывать символы слева. При встрече левой скобки заносим её позицию в стек. Когда появляется правая скобка, извлекаем данные из стека. Так определяем позицию последней левой скобки.
Также стек можно использовать при поиске в глубину. Это метод, который мы рассмотрим в разделе 4.3. В нём среди элементов для поиска всегда выбирается самый последний.
Реализация через collections.deque
Стек можно реализовать с помощью класса deque из модуля collections. Deque имеет более быстрые операции добавления и извлечения элементов с обоих концов контейнера.
from collections import deque
stack = deque()
# push
stack.append("Blue")
stack.append("Green")
stack.append("Red")
print("Стек:", stack)
# pop
print("pop ->", stack.pop())
print("pop ->", stack.pop())
print("Стек после pop:", stack)Реализация через queue.LifoQueue
В модуле queue есть структура данных LifoQueue.
В этом модуле доступны различные функции:
- maxsize — допустимое количество элементов в очереди.
- empty() — возвращает True, если очередь пуста, в противном случае — False.
- full() — возвращает True, если очередь заполнена.
- get() — удаляет и возвращает элемент из очереди. Если очередь пуста, ожидает появления элемента.
- get_nowait() — возвращает элемент, если он доступен сразу; в противном случае вызывает исключение Empty.
- put(item) — помещает элемент в очередь. Если очередь заполнена, ожидает освобождения места.
- put_nowait(item) — помещает элемент в очередь без ожидания. Если свободных мест нет, вызывает исключение Full.
- qsize() — возвращает количество элементов в очереди.
from queue import LifoQueue
stack = LifoQueue(maxsize=3)
# добавление элементов в стек
stack.put('a')
# извлечение и удаление элементов
element = stack.get()