Как реализовать добавление и удаление элементов в очереди Python

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

Знаете ли вы, какую структуру взять под очередь и почему не список. Следом почти всегда спрашивают про сложность операций и про очередь между потоками или корутинами.

Как отвечать

Базовый ответ: collections.deque. Добавление в конец append, извлечение из начала popleft, обе операции O(1). Несколько элементов сразу добавляет extend. Извлечение из пустой очереди бросает IndexError, поэтому перед popleft проверяют if q: или ловят исключение.

Дальше покажите, что выбор зависит от задачи:

• list: append дешёвый, но pop(0) сдвигает все элементы и стоит O(n). На большой очереди это заметно;
• deque(maxlen=N): ограниченный буфер, при переполнении старый элемент молча выпадает с другого конца. Удобно для «последних N событий», опасно, если терять данные нельзя;
• queue.Queue: для потоков. put и get блокируются с таймаутом, maxsize ограничивает размер, get_nowait бросает queue.Empty, а task_done вместе с join позволяют дождаться обработки всех задач. С Python 3.13 есть shutdown() для корректной остановки;
• asyncio.Queue: то же для корутин, await q.get(). Потокобезопасной она не является;
• PriorityQueue и heapq: когда порядок задаёт приоритет, а не время добавления;
• multiprocessing.Queue: между процессами, объекты сериализуются через pickle.

Если просят реализовать очередь самостоятельно, покажите вариант на двух стеках: амортизированно O(1) на операцию. Хорошо добавить, что deque устроен как двусвязный список блоков, поэтому доступ по индексу в середину у него O(n).

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

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

Используют deque как канал между потоками. Сами append и popleft атомарны, но ждать появления элемента deque не умеет, и потребитель крутится в пустом цикле.

Вызывают queue.Queue.get() внутри асинхронного кода. Блокирующий вызов останавливает весь цикл событий, здесь нужна asyncio.Queue.