Какой тип данных использовать для хранения очереди в Python

Что проверяют

Знаете ли вы, что список плохо подходит для очереди, и различаете ли структуру данных и механизм передачи задач между потоками. Уточнение почти всегда такое: а если читают и пишут из разных потоков или корутин?

Как отвечать

Ответ зависит от того, кто работает с очередью:

• collections.deque: выбор для одного потока. append и popleft работают за O(1), а list.pop(0) сдвигает все элементы и стоит O(n). Параметр maxlen превращает deque в кольцевой буфер: при переполнении старые элементы молча выпадают с другого конца;
• queue.Queue: очередь для потоков. get() по умолчанию ждёт элемент, put() при заданном maxsize ждёт свободное место, пара task_done() и join() позволяет дождаться обработки всех задач;
• asyncio.Queue: то же для корутин, get и put вызываются через await. Потокобезопасной она не является;
• multiprocessing.Queue: передача между процессами, объекты сериализуются через pickle;
• приоритеты: heapq поверх списка или queue.PriorityQueue, если нужна потокобезопасность.

Покажите, что понимаете границы deque. Отдельные append и popleft в CPython атомарны, но блокирующего ожидания у deque нет: на пустой очереди popleft() бросает IndexError, и потребителю пришлось бы опрашивать её в цикле. queue.Queue решает именно это: поток спит, пока не появится работа. Доступ к середине deque по индексу, наоборот, медленный.

Назовите и ограничение размера: maxsize даёт обратное давление, и быстрый производитель не забьёт память, пока потребитель отстаёт.

Где спотыкаются

Используют list с pop(0) на больших объёмах. На десятке элементов разницы нет, на сотнях тысяч очередь становится узким местом.

Кладут deque между потоками и пишут цикл «проверить, поспать, проверить». Это жжёт процессор и добавляет задержку, хотя queue.Queue с блокирующим get() делает то же без опроса.

Обращаются к asyncio.Queue из другого потока. Прямой вызов не потокобезопасен, ожидающая корутина может так и не проснуться. Правильный путь: loop.call_soon_threadsafe(queue.put_nowait, item).