Очередь — Алгоритмы и структуры данных

Очередь

Структура FIFO: первым пришёл — первым вышел.

Сигнатураenqueue/dequeue O(1)

Очередь работает по принципу FIFO (first in, first out): добавление в хвост, извлечение из головы. Применяется в обходе в ширину, планировщиках задач и буферах. В Python используйте collections.deque, чтобы извлечение из головы было O(1), а не O(n) как у списка.

Сложность: enqueue и dequeue — O(1). Память: O(n).

from collections import deque
q = deque()
q.append(1)        # enqueue
q.append(2)
x = q.popleft()    # dequeue -> 1 (FIFO)
print(x, q)        # 1 deque([2])

← Все записи: Алгоритмы и структуры данных