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

очередью вы удаляете элемент, который был добавлен в нее 
раньше всех (принцип «первым пришел — первым ушел», или FIFO); одна-
ко в случае со 
стеком вы удаляете элемент, который был добавлен в него 
позже всех (принцип «последним пришел — первым ушел», или LIFO).
С точки зрения производительности предполагается, что надлежащая 
реализация очереди будет занимать O(1) времени на операции вставки 
и удаления. Эти две выполняемые с очередью операции являются глав-

---

192 Глава 5 • Общие структуры данных Python
ными, и при правильной реализации они обеспечивают высокое быстро-
действие.
Очереди находят широкое применение в алгоритмах и нередко помогают 
решать задачи планирования и параллельного программирования. Корот-
кий и красивый алгоритм с использованием очереди представлен поис-
ком в ширину (breadth-first search, BFS) на древовидной или графовой 
структуре данных.
В алгоритмах планирования выполнения задач во внутреннем представ-
лении нередко используются очереди с приоритетом. Они представля-
ют собой специализированные очереди: вместо получения следующего 
элемента по времени вставки очередь с приоритетом получает элемент 
с самым высоким приоритетом. Приоритет отдельных элементов опреде-
ляется очередью, основанной на примененном к их ключам упорядочении. 
В следующем разделе мы обратимся к очередям с приоритетом и рассмо-
трим ближе, как они реализуются в Python.
Однако в обычной очереди содержащиеся в ней элементы не переупоря-
дочиваются. Точно так же, как и в примере с конвейером, «вы получите 
только то, что вы вставили», и именно в таком порядке.
Python поставляется с несколькими реализациями очереди, каждая из ко-
торых обладает несколько различающимися характеристиками. Давайте 
их рассмотрим.
list — ужасно меееедленная очередь
В качестве очереди можно использовать обычный список, но с точки 
зрения производительности такое решение не идеально
1
. Списки для 
этой цели довольно медленные, потому что вставка в начало очереди или 
удаление элемента влекут за собой сдвиг всех других элементов на одну 
позицию, требуя O(n) времени.
Поэтому я не рекомендую использовать список в качестве импровизиро-
ванной очереди в Python (если только вы не имеете дело с небольшим 
количеством элементов).
1
См. документацию Python «Применение списков в качестве очередей»: 
https://docs .
python .org/3/tutorial/datastructures .html#using-lists-as-queues

---

5 .6 . Очереди (с дисциплиной доступа FIFO) 193
>>> q = [] 
>>> q.append('есть') 
>>> q.append('спать') 
>>> q.append('программировать') 
>>> q 
['есть', 'спать', 'программировать'] 
# Осторожно: это очень медленная операция! 
>>> q.pop(0) 
'есть'
collections .deque — быстрые и надежные очереди
Класс 
deque
реализует очередь с двусторонним доступом, которая под-
держивает добавление и удаление элементов с любого конца за O(1) 
(неамортизируемое) время. Поскольку двусторонние очереди одинаково 
хорошо поддерживают добавление и удаление элементов с любого конца, 
они могут служить в качестве очередей и в качестве стеков
1
.
Объекты Python 
deque
реализованы как двунаправленные связные списки 
(doubly-linked lists)
2
. Это придает им превосходную и стабильную произ-
водительность для операций вставки и удаления элементов, но при этом 
плохую O(n) производительность для произвольного доступа к элементам 
в середине очереди.
Как результат, двусторонняя очередь 
collections.deque
будет хорошим 
выбором, если вы ищете структуру данных очередь в стандартной библио-
теке Python.
>>> from collections import deque 
>>> q = deque() 
>>> q.append('есть') 
>>> q.append('спать') 
>>> q.append('программировать')
1
См. документацию Python «collections.deque»: 
https://docs .python .org/3 .6/library/collections .
html#collections .deque
2
См. CPython «_collectionsmodule.c»: 
https://github .com/python/cpython/blob/master/Modules/_
collectionsmodule .c

---

194 Глава 5 • Общие структуры данных Python
>>> q 
deque(['есть', 'спать', 'программировать'])
>>> q.popleft()