Почему очередь, сделанная через список, медленно работает в Python

Очередь через список (list) медленная, потому что операции pop(0) и insert(0, ...) имеют сложность O(n). При удалении или вставке элемента в начало списка Python вынужден сдвигать все остальные элементы, что сильно замедляет работу при больших объемах данных.

Пример:

queue = []
queue.append(1)  # O(1) – в конец
queue.pop(0)     # O(n) – удаление из начала

Решение:
Используйте collections.deque – он оптимизирован для операций с обоих концов (popleft() и appendleft() работают за O(1)):

from collections import deque
queue = deque()
queue.append(1)    # O(1)
queue.popleft()    # O(1)