Б41 Чистый Python. Тонкости программирования для профи. Спб.: Питер

'программировать' 
>>> s.pop() 
'спать' 
>>> s.pop() 
'есть' 
>>> s.pop() 
IndexError: "pop from an empty deque"
deque .LifoQueue — семантика блокирования 
для параллельных вычислений
Данная реализация стека в стандартной библиотеке Python синхрони-
зирована и обеспечивает семантику блокирования с целью поддержки 
многочисленных параллельных производителей и потребителей
1
.
Помимо 
LifoQueue
, модуль 
queue
содержит несколько других классов, 
которые реализуют очереди с мультипроизводителями/мультипотреби-
телями, широко используемые в параллельных вычислениях.
В зависимости от вашего варианта использования семантика блокирова-
ния может оказаться полезной, а может накладывать ненужные издержки. 
В этом случае в качестве стека общего назначения лучше всего использо-
вать список 
list
или двустороннюю очередь 
deque
.
>>> from queue import LifoQueue 
>>> s = LifoQueue() 
>>> s.put('есть') 
1
См. документацию Python «queue.LifoQueue»: 
https://docs .python .org/3 .6/library/queue .html

---

5 .5 . Стеки (с дисциплиной доступа LIFO) 189
>>> s.put('спать') 
>>> s.put('программировать')
>>> s 

>>> s.get() 
'программировать' 
>>> s.get() 
'спать' 
>>> s.get() 
'есть' 
>>> s.get_nowait() 
queue.Empty 
>>> s.get() 
# Блокирует / ожидает бесконечно...
Сравнение реализаций стека в Python
Как вы убедились, Python поставляется с несколькими реализациями 
стековой структуры данных. Все они обладают слегка различающимися 
характеристиками, а также компромиссным соотношением производи-
тельности и применения.
Если вам не нужна поддержка параллельной обработки (или вы не хотите 
обрабатывать блокировку и снятие блокировки вручную), то ваш выбор 
сводится к встроенному типу 
list
или 
collections.deque
. Разница лежит 
в используемой за кадром структуре данных и общей простоте использо-
вания:
‰
‰
Список 
list
поддерживается динамическим массивом, который делает 
его отличным выбором для быстрого произвольного доступа, но при 
этом требует нерегулярного изменения размеров во время добавления 
или удаления элементов. Список выделяет излишнюю резервную 
память, чтобы не каждая операция вталкивания и выталкивания тре-
бовала изменения размеров, и для этих операций вы получаете амор-

---

190 Глава 5 • Общие структуры данных Python
тизируемую временную сложность O(1). Однако вам следует быть 
внимательными и стараться выполнять вставку и удаление элементов 
«с правильной стороны», используя методы 
append()
и 
pop()
. В про-
тивном случае производительность замедлится до O(n).
‰
‰
Двусторонняя очередь 
collections.deque
поддерживается двунаправ-
ленным связным списком, который оптимизирует добавления и уда-
ления с обоих концов и обеспечивает для этих операций стабильную 
производительность O(1). Производительность класса 
deque
не только 
стабильнее, но его также легче использовать, потому что вам не при-
ходится переживать по поводу добавления или удаления элементов 
«не с того конца».
Резюмируя, я полагаю, что двусторонняя очередь 
collections.deque
представляет собой отличный вариант для реализации стека (очереди 
LIFO) на Python.
Ключевые выводы
‰
‰
Python поставляется с несколькими реализациями стека, которые 
обладают слегка различающимися характеристиками производитель-
ности и особенностями использования.
‰
‰
Двусторонняя очередь 
collections.deque
обеспечивает безопасную 
и быструю реализацию стека общего пользования.
‰
‰
Встроенный тип 
list
может применяться в качестве стека, но следует 
соблюдать осторожность и добавлять и удалять элементы только при 
помощи методов 
append()
и 
pop()
, чтобы избежать замедления произ-
водительности.
5 .6 . Очереди (с дисциплиной доступа FIFO)
В этом разделе вы увидите, как реализовывать очередь, то есть структуру 
данных с дисциплиной доступа FIFO, используя только встроенные типы 
данных и классы из стандартной библиотеки Python. Но сначала давайте 
вкратце повторим, что такое очередь.

---

5 .6 . Очереди (с дисциплиной доступа FIFO) 191
Очередь представляет собой коллекцию объектов, которая поддерживает 
быструю семантику доступа «первым пришел — первым ушел» (FIFO — first 
in, first out) для вставок и удалений. Операции вставки и удаления иногда 
называются поставить в очередь (enqueue) и убрать из очереди (dequeue). 
В отличие от списков или множеств, очереди, как правило, не допускают 
произвольного доступа к объектам, которые они содержат.
Ниже приведена аналогия для очереди с дисциплиной доступа «первым 
пришел — первым ушел» из реального мира:
Представьте очередь разработчиков-питонистов, ожидающих получе-
ния значка участника конференции в день регистрации на PyCon . По 
мере прибытия новых участников к месту проведения конференции они 
выстраиваются в очередь, «становясь в ее конец», чтобы получить свои 
значки . Удаление (обслуживание) происходит в начале очереди, когда 
разработчики получают свои значки и пакет с материалами и подарками 
конференции и покидают очередь .
Еще один способ запомнить особенности структуры данных очередь со-
стоит в том, чтобы представить ее как конвейер:
Новые элементы (молекулы воды, теннисные мячи, …) вставляются 
в одном конце и проходят в другой, где вы или кто-то другой их все 
время удаляете . Когда элементы находятся в очереди (в твердой ме-
таллической трубе), вы не можете до них добраться . Единственный спо-
соб взаимодействия с элементами из очереди заключается в том, чтобы 
добавлять новые элементы в конец (ставить в очередь) или удалять 
элементы из начала конвейера (убирать из очереди) .
Очереди похожи на стеки, и разница между ними в том, как удаляются 
элементы.
В случае с