Что такое очередь (queue) и как работают enqueue/dequeue?
Читаю про очереди и немного путаюсь. Понял, что это FIFO — кто первый пришёл, тот первый ушёл, как в магазине. Но как это реализовать в Python нормально? Видел, что используют обычный список, но кто-то говорил, что это плохо. Можете объяснить на пальцах, что такое enqueue и dequeue и где очереди реально применяют?
2 ответа
Хороший вопрос, давай по порядку.
Очередь (queue) — это структура данных, которая работает по принципу FIFO (First In, First Out): первый добавленный элемент будет первым извлечён. Аналогия с очередью в магазине у тебя абсолютно верная.
Две базовые операции:
- enqueue — добавить элемент в хвост очереди.
- dequeue — извлечь элемент из головы очереди.
Теперь про реализацию. Списком list пользоваться можно, но pop(0) для извлечения из начала работает за O(n) — Python физически сдвигает все оставшиеся элементы влево. На больших объёмах это убивает производительность.
Правильный инструмент — collections.deque. У него извлечение из обоих концов за O(1):
from collections import deque
queue = deque()
# enqueue — добавляем в хвост
queue.append("Аня")
queue.append("Боря")
queue.append("Вика")
# dequeue — забираем из головы
first = queue.popleft() # 'Аня'
print(first, list(queue)) # Аня ['Боря', 'Вика']
Почему deque быстрее? Внутри это двусвязный блок-список, а не один непрерывный массив, поэтому добавление/удаление с краёв не требует сдвига.
Где применяют очереди:
- BFS (обход графа в ширину) — соседей кладём в очередь и обрабатываем по порядку.
- Буферы и task-очереди (обработка задач в порядке поступления).
- Очереди печати, обработка событий.
Итог: для очереди всегда бери deque, а list.pop(0) оставь в прошлом.
Добавлю практическую деталь: если тебе нужна потокобезопасная очередь (несколько потоков пишут/читают), то бери не deque, а queue.Queue из стандартной библиотеки — там уже встроены блокировки.
from queue import Queue
q = Queue()
q.put(1) # enqueue
x = q.get() # dequeue
Но для однопоточного кода и алгоритмов (тот же BFS) collections.deque быстрее и проще — лишние локи не нужны.
