Очередь в Python: реализация и лучшие практики

человек держит книгу по Python

TL;DR

Очередь — простая линейная структура данных по принципу FIFO. В Python её можно реализовать и на списке (list), и на collections.deque. Для учебных задач и небольшого числа операций list годится, для масштабных очередей и частых удалений с начала используйте deque.

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

Image Credit:

Wikipedia

Очередь — это линейная структура данных, работающая по принципу FIFO (First-In-First-Out): первый добавленный элемент вытесняется первым. По сути, это как очередь в магазине: первый пришёл — первым обслужен.

Кратко — основные операции очереди:

Enqueue: добавление элемента в конец очереди.
Dequeue: удаление элемента из начала очереди.
Print: вывод содержимого очереди.
Front: получение элемента в начале очереди без удаления.
Rear: получение элемента в конце очереди без удаления.

Важно: разные реализации дают разную сложность операций. Ниже — реализация на list и рекомендации.

Как реализовать очередь на list (базовый учебный пример)

В этом разделе показан интерактивный пример, где программа принимает команды от пользователя и выполняет операции с очередью, реализованной на списке.

queue = []

while True:
    command = input("What do you want to do?\n")

    if command == "enqueue":
        enqueue = int(input("Enter the element to Enqueue: "))
        queue.append(enqueue)
    elif command == "dequeue":
        if len(queue) == 0:
            print("Queue is empty")
        else:
            queue.pop(0)
    elif command == "print":
        print(queue)
    elif command == "front":
        if len(queue) == 0:
            print("Queue is empty")
        else:
            print(queue[0])
    elif command == "rear":
        if len(queue) == 0:
            print("Queue is empty")
        else:
            print(queue[len(queue) - 1])
    else:
        break

print(queue)

Пояснения к коду:

Создаётся пустой список queue.
В бесконечном цикле while True программа спрашивает команду и выполняет соответствующую операцию.
Для enqueue используется append — быстрый амортизированный O(1).
Для dequeue используется pop(0) — дорогостоящая операция O(n), так как приходится сдвигать все элементы.

Важно

Этот учебный пример рабочий и прост для понимания, но при интенсивных операциях dequeue реализация на list становится неэффективной.

Почему pop(0) на list медленный и что с этим делать

Если вы много раз удаляете элементы с начала списка, каждый pop(0) требует сдвига всех оставшихся элементов — это O(n) на каждый вызов. При миллионах операций суммарное время растёт квадратично.

Альтернатива: коллекция deque из модуля collections. Она реализована как двусторонняя очередь и поддерживает append и popleft за O(1).

from collections import deque

queue = deque()

queue.append(10)   # enqueue
queue.append(20)
queue.append(30)
queue.popleft()     # dequeue
print(queue)

Сравнение сложностей (ориентировочно):

list.append: O(1) амортизированно
list.pop(0): O(n)
deque.append: O(1)
deque.popleft: O(1)

Факт-бокс

deque — рекомендуемая структура для очередей в Python, когда ожидается частая работа с концами.
list подходит для редких операций удаления с начала или для небольших объёмов данных.

Когда реализация на list не подходит (контрпримеры)

Когда программа получает потоковое событие и каждое событие dequeuel’ится: pop(0) приведёт к заметным задержкам.
Когда очередь используется как буфер между потоками данных и требуется высокая пропускная способность.
Когда нужно многопоточное безопасное поведение: deque можно использовать с блокировкой или queue.Queue для потокобезопасности.

Альтернативные подходы

collections.deque — для высокой производительности и простоты.
queue.Queue — для межпоточного взаимодействия (имеет блокирующие put/get и опциональный размер).
multiprocessing.Queue — для процессов.
Специализированные очереди (например, Redis list) — для распределённых систем.

Ментальная модель и эвристики выбора

“Если удаляете с начала часто — используйте deque”.
“Если нужна блокировка и ожидание — используйте queue.Queue”.
“Если очередь маленькая и простая — list с append/pop(0) проще понять и отлаживать”.

Mermaid: простая логика выбора реализации

flowchart TD
  A[Нужна очередь?] --> B{Частые удаления с начала?}
  B -- Да --> C{Межпоточное взаимодействие?}
  B -- Нет --> D[Можно использовать list]
  C -- Да --> E[Используйте queue.Queue]
  C -- Нет --> F[Используйте collections.deque]

Критерии приёмки (тесты и примеры)

При добавлении 3 элементов, последовательный dequeue возвращает их в том же порядке.
Попытка dequeue пустой очереди должна корректно обрабатываться (не падать с исключением без объяснения).
Операции front/rear не удаляют элементы.
Для deque-реализации время выполнения 1000 popleft заметно меньше, чем для list pop(0).

Примеры тест-кейсов

Добавить [1,2,3], вызвать dequeue три раза — получить 1,2,3.
Вызвать front на пустой очереди — получить сообщение, что очередь пустая.
Для списка выполнить 10000 enqueue и 10000 dequeue и убедиться, что время значительно больше, чем у deque.

Шаблон: контрольный список для собеседования (роль: кандидат Python)

Могу объяснить разницу между list и deque для очереди.
Знаю сложности основных операций (append, pop(0), popleft).
Могу предложить queue.Queue для многопоточной среды.
Могу привести пример кода для каждой реализации.
Понимаю, когда нужен внешний брокер очередей (RabbitMQ, Redis) для масштабирования.

Короткие примеры: queue.Queue и многопоточность

from queue import Queue
from threading import Thread

q = Queue()

# Producer
q.put(1)

# Consumer
item = q.get()
q.task_done()

queue.Queue — потокобезопасная и блокирующая реализация, удобна для producer-consumer паттерна.

Глоссарий (одна строка)

FIFO — First-In-First-Out, порядок, при котором первый добавленный элемент извлекается первым.
enqueue — операция добавления в очередь.
dequeue — операция удаления из очереди.
deque — двусторонняя очередь (collections.deque).

Часто задаваемые вопросы

Чем отличается deque от queue.Queue?

deque — структура данных (быстрая работа с краями), но не потокобезопасна по умолчанию. queue.Queue — потокобезопасная, поддерживает блокирующие операции и опциональный максимальный размер.

Когда использовать list вместо deque?

Когда объёмы данных малы и количество операций удаления с начала невелико. Для демонстраций и обучения list понятнее новичкам.

Что лучше для распределённого приложения?

Для распределённых систем лучше использовать внешние очереди типа Redis, RabbitMQ или Kafka.

Итог

Очередь — простая, но ключевая структура данных.
Для реальных приложений предпочтительнее collections.deque или специализированные очереди (queue.Queue для потоков, внешние брокеры для распределённых систем).
На собеседовании важно уметь объяснить различия по сложности и привести пример кода.

Summary