Как реализовать очередь FIFO на Python

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

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

Как отвечать

Начните с цены наивного варианта, потом инструменты:

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

Если просят написать класс руками, оберните deque: методы enqueue, dequeue, __len__, понятное исключение на пустой очереди. Можно упомянуть кольцевой буфер с индексами головы и хвоста.

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

Используют list с pop(0) или insert(0, x) в паре с pop(). Это та же линейная стоимость, просто с другого конца.

Гоняют deque между потоками в цикле if q: q.popleft(). Операции у deque атомарны, но ждать элемента она не умеет, и такой цикл съедает процессор. Для этого и существует queue.Queue.

Пишут if not q.empty(): q.get() в многопоточном коде. Между проверкой и get другой поток может забрать элемент, поэтому empty() и qsize() дают лишь примерную картину. Правильно вызвать get(timeout=...) и обработать queue.Empty. Родственная ошибка: класть в asyncio.Queue из другого потока без loop.call_soon_threadsafe.