очередью вы удаляете элемент, который был добавлен в нее
раньше всех (принцип «первым пришел — первым ушел», или 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()
Do'stlaringiz bilan baham: |