Очередь работает по правилу "первым пришёл, первым ушёл" (FIFO): элемент добавляется в конец, а извлекается из начала. Выглядит просто, но наивная реализация платит скрытый O(n). В этом уроке мы построим три правильные реализации: на списке, на связном списке и на кольцевом буфере.
Операции
Основные операции ADT очереди: enqueue(x), dequeue(), peek(), is_empty(). Цель — выполнять каждую за O(1). В отличие от стека, добавление и извлечение идут с противоположных концов, поэтому одного конца списка недостаточно.
Почему list.pop(0) плох
list в Python — это массив (память массива). Когда убирают первый элемент, остальные n - 1 сдвигаются на одну ячейку влево. Ниже модель, которая считает сдвиги вручную, без таймера; n вызовов pop(0) дают O(n²). Цены встроенных операций смотрите в этой таблице.
def pop_front_moves(items):
moves = 0
for i in range(1, len(items)):
items[i - 1] = items[i]
moves += 1
items.pop()
return moves
for n in (10, 100, 1000):
print(n, pop_front_moves(list(range(n))))10 9
100 99
1000 999