image_pdf

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

Вот реальная аналогия для очереди первого входа, первого выхода:

Представьте себе очередь питонистов, ожидающих, чтобы забрать свои значки конференции в первый день регистрации PyCon. Новые дополнения к очереди вносятся в заднюю часть очереди, когда новые люди входят в место проведения конференции и” выстраиваются в очередь», чтобы получить свои значки. Удаление (обслуживание) происходит в передней части очереди, так как разработчики получают свои значки и сумки для конференций swag и покидают очередь.

Еще один способ запомнить характеристики структуры данных очереди-это думать о ней как о канале:

Новые предметы (молекулы воды, шарики для пинг-понга,…) помещаются в один конец и перемещаются в другой, где вы или кто-то другой снова их удаляет. В то время как предметы находятся в очереди, сплошная металлическая труба, вы не можете добраться до них. Единственный способ взаимодействия с элементами в очереди-это добавление новых элементов в конце ( очередь ) или удаление элементов в передней части (удаление очереди ) канала.

Очереди похожи на стеки, и разница между ними заключается в удалении элементов:

С помощью очереди вы удаляете элемент, добавленный последним (первый вход, первый выход или FIFO); а с помощью стека вы удаляете элемент, добавленный последним ( последний вход, первый выход или LIFO).

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

Очереди имеют широкий спектр применения в алгоритмах и для решения задач планирования, а также параллельного программирования. Короткий и красивый алгоритм, использующий очередь, — это широтно-первый поиск (BFS) в структуре данных дерева или графика.
Алгоритмы планирования часто используют внутренние очереди приоритетов. Это специализированные очереди: вместо получения следующего элемента по времени вставки приоритетная очередь получает элемент с наивысшим приоритетом. Приоритет отдельных элементов определяется очередью на основе порядка, применяемого к их ключам.

Обычная очередь, однако, не будет повторно заказывать элементы, которые она несет. Вы получаете то, что вы вкладываете, и именно в таком порядке (помните пример с трубой?)

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

Встроенный список list

Можно использовать обычный listв качестве очереди, но это не идеально с точки зрения производительности . Списки для этой цели довольно медленны, потому что вставка или удаление элемента в начале требует сдвига всех других элементов на один, требуя O(n) времени.

Поэтому я бы не рекомендовал вам использовать a listв качестве временной очереди в Python (если вы не имеете дело только с небольшим количеством элементов).

# How to use Python's list as a FIFO queue:

q = []

q.append('eat')
q.append('sleep')
q.append('code')

>>> q
['eat', 'sleep', 'code']

# Careful: This is slow!
>>> q.pop(0)
'eat'

Класс collections.deque

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

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

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

collections.deque это отличный выбор по умолчанию, если вы ищете структуру данных очереди в стандартной библиотеке Python.

# How to use collections.deque as a FIFO queue:

from collections import deque
q = deque()

q.append('eat')
q.append('sleep')
q.append('code')

>>> q
deque(['eat', 'sleep', 'code'])

>>> q.popleft()
'eat'
>>> q.popleft()
'sleep'
>>> q.popleft()
'code'

>>> q.popleft()
IndexError: "pop from an empty deque"

Класс queue.Queue

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

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

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

# How to use queue.Queue as a FIFO queue:

from queue import Queue
q = Queue()

q.put('eat')
q.put('sleep')
q.put('code')

>>> q


>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get_nowait()
queue.Empty

>>> q.get()
# Blocks / waits forever...

Класс multiprocessing.Queue

Это реализация общей очереди заданий, которая позволяет помещенным в очередь элементам обрабатываться параллельно несколькими параллельными работниками. Распараллеливание на основе процессов популярно в Python из-за глобальной блокировки интерпретатора (GIL) .

multiprocessing.Queue предназначена для совместного использования данных между процессами и может хранить любой маринованный объект.

# How to use multiprocessing.Queue as a FIFO queue:

from multiprocessing import Queue
q = Queue()

q.put('eat')
q.put('sleep')
q.put('code')

>>> q


>>> q.get()
'eat'
>>> q.get()
'sleep'
>>> q.get()
'code'

>>> q.get()
# Blocks / waits forever...

Хороший выбор по умолчанию: collections.deque
Если вы не ищете поддержку параллельной обработки, предложенная реализация collections.deque является отличным выбором по умолчанию для реализации структуры данных очереди FIFO в Python.

I’D предоставляет характеристики производительности, которые вы ожидаете от хорошей реализации очереди, а также может использоваться в качестве стека (очередь LIFO).

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

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

Source

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

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

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

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