image_pdf

Как реализовать структуру данных стека (LIFO) в Python, используя только встроенные типы и классы из стандартной библиотеки?

Cтек — это набор объектов, который поддерживает правило last in, first out или «последний пришел, первый вышел» (LIFO) для вставок и удалений. В отличие от списков или массивов, стеки обычно не допускают произвольного доступа к содержащимся в них объектам. Операции вставки и удаления также часто называются push и pop.

Вот вам аналогия для структуры стековых данных из реальной жизни — стопка пластинок:

Новые пластинки складываются наверх стопки. А поскольку пластинки хрупкие и представляют великую ценность для меломанов, то можно снимать только самую верхнюю пластинку (последний пришел, первый вышел). Чтобы достать пластинку снизу, необходимо одну за другой снять самые верхние пластинки.

Стеки и очереди похожи. Они представляют собой линейные коллекции объектов, а разница заключается в порядке доступа к объектам: в очереди вы удаляете самые ранний добавленный объект (first-in, first-out или FIFO); а в стеке наоборот вы удаляете последний добавленный объект (last-in, first-out или LIFO),

С точки зрения производительности ожидается, что при правильной реализации стека потребуется O(1) времени для вставки и удаления.

Стек используется во многих алгоритмах, от, например, синтаксического анализа языка до управления памятью («стек вызовов»). Короткий и красивый алгоритм с использованием стека — поиск в глубину (DFS) в деревьях и графах.

В Python есть несколько реализаций стека, каждая из которых имеет свои особенности. Давайте посмотрим на них:

Cписок — list

Тип данных list вполне себе приличная структура для организации стека, имеет операции push и pop, выполняющиеся за время O(1).

По сути, списки являются динамическими массивами и им иногда необходимо изменить размер пространства для хранения элементов при добавлении или удалении. В списке происходит перераспределение памяти, так что не каждый push или pop требует изменения размера, отсюда и получается оценка O(1) для этих операций.

Недостатком является то, что производительность не стабильна и нельзя сказать, что при вставке и удалении она всегда O(1), как в реализации на основе связанного списка (например, collection.deque, см. ниже). С другой стороны, быстрый доступ к случайному элементу с производительностью O(1) может быть дополнительным преимуществом.

Важное предупреждение относительно производительности: при использовании списков в качестве стеков для стабильной производительности O(1) вставки и удаления необходимо добавлять новые элементы в конец списка с помощью метода append(), удаляя при этом хвост, используя pop(). Стеки, основанные на списках Python, растут вправо и сжимаются слева.

Добавление и удаление в начало происходит намного медленнее и занимает O(n) времени, так как существующие элементы должны быть смещены по кругу для освобождения место для нового элемента.

# How to use a Python list as a stack (LIFO):
s = []
s.append('eat')
s.append('sleep')
s.append('code')
>>> s
['eat', 'sleep', 'code']
>>> s.pop()
'code'
>>> s.pop()
'sleep'
>>> s.pop()
'eat'
>>> s.pop()
IndexError: "pop from empty list"

Класс collections.deque

Класс deque реализует двустороннюю очередь, которая поддерживает добавление и удаление элементов с любого конца за время O(1).

Поскольку двусторонние очереди одинаково хорошо поддерживает добавление и удаление элементов с обоих концов, то они могут служить и очередями, и стеками.

Объекты deque в Python реализованы в виде двусвязных списков, что дает им отличную и стабильную производительность для вставки и удаления элементов, но низкую производительность O(n) для случайного доступа к элементам в середине стека.

collection.deque — отличный выбор из стандартной библиотеки Python для реализации стека с характеристиками производительности связанного списка.

# How to use collections.deque as a stack (LIFO):
from collections import deque
q = deque()
q.append('eat')
q.append('sleep')
q.append('code')
>>> q
deque(['eat', 'sleep', 'code'])
>>> q.pop()
'code'
>>> q.pop()
'sleep'
>>> q.pop()
'eat'
>>> q.pop()
IndexError: "pop from an empty deque"

Класс queue.LifoQueue

Эта реализация стека в стандартной библиотеке Python синхронизирована и обеспечивает семантику блокировки для поддержки нескольких одновременно работающих процессов.

Модуль queue содержит несколько других классов, реализующих многопоточные и многопользовательские очереди, которые полезны для параллельных вычислений.

В зависимости от варианта использования блокировки может оказаться полезной или просто повлечь за собой ненужные накладные расходы. В этом случае вам лучше использовать list или deque в качестве стека общего назначения.

# How to use queue.LifoQueue as a stack:
from queue import LifoQueue
s = LifoQueue()
s.put('eat')
s.put('sleep')
s.put('code')
>>> s
<queue.LifoQueue object at 0x108298dd8>
>>> s.get()
'code'
>>> s.get()
'sleep'
>>> s.get()
'eat'
>>> s.get_nowait()
queue.Empty
>>> s.get()
# Blocks / waits forever...

Лучший выбор по умолчанию: collections.deque

Если нет необходимости параллельной обработки (или ручной блокировки и разблокировки), то выбор сводится к встроенному типу list или collection.deque. Разница заключается в структуре данных «под капотом» и в простоте использования.

  • list есть динамический массив, который отлично подходит для быстрого произвольного доступа, но требует периодического изменения размера при добавлении или удалении элементов. Список перераспределяет свое пространство хранения, так что не каждый push или pop требует изменения размера, обеспечивая производительность O(1). Но нужно быть осторожным при вставке и удалении элементов только справа (append и pop), иначе произойдёт снижение производительности до O(n).
  • collection.deque является двусвязным списком, который оптимизирован для добавления и удаления с любой стороны и обеспечивает одинаковую производительность O(1) для этих операций. Производительность не только стабильна, но и сам класс deque проще, поскольку не нужно беспокоиться о добавлении или удалении элементов с «неправильного конца».

Исходя из этих соображений collection.deque является отличным выбором для реализации стека (очереди LIFO) в Python.

Ознакомьтесь с полной серией статей «Основные структуры данных в Python».

В этой статье чего-то не хватает или вы нашли ошибку? Помогите коллеге и оставьте комментарий ниже.

Source

Опубликовано Вадим В. Костерин

Ст.преп. кафедры ИТЭ. Автор более 130 научных и учебно-методических работ. Лауреат ВДНХ (серебряная медаль).

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *