Когда в Python следует использовать collections.deque вместо списка?

collections.deque (двусторонняя очередь) следует использовать вместо списка (list), когда требуется быстрое добавление и удаление элементов с обоих концов коллекции.

Ключевое отличие: Производительность

• deque: Операции append, pop, appendleft, popleft имеют амортизированную сложность O(1).
• list: append и pop (с конца) также имеют сложность O(1), но insert(0, ...) и pop(0) (с начала) требуют сдвига всех элементов и имеют сложность O(n).

Основные сценарии использования deque:

1. Реализация очередей (FIFO): Использовать append для добавления и popleft для извлечения.
2. Скользящее окно: Хранение N последних элементов из потока данных с помощью параметра maxlen.
3. Алгоритмы обхода графов (BFS): Где требуется эффективная очередь для хранения вершин.

Пример:

from collections import deque

# 1. Быстрые операции с обоих концов
d = deque([1, 2, 3])
d.appendleft(0)  # O(1) -> deque([0, 1, 2, 3])
d.append(4)      # O(1) -> deque([0, 1, 2, 3, 4])
d.popleft()      # O(1) -> возвращает 0, d = deque([1, 2, 3, 4])

# 2. Ограничение размера (скользящее окно)
last_five_logs = deque(maxlen=5)
for i in range(10):
    last_five_logs.append(f"Log entry {i}")

# deque автоматически удаляет старые элементы
print(last_five_logs) 
# Вывод: deque(['Log entry 5', 'Log entry 6', 'Log entry 7', 'Log entry 8', 'Log entry 9'], maxlen=5)

Вывод: Если вам нужна структура данных, оптимизированная для операций в начале и в конце, deque — лучший выбор. Для произвольного доступа по индексу и операций в середине коллекции list остается более эффективным.