Дек (deque): очередь с двух концов и зачем она нужна

Коротко

Дек (deque, от double-ended queue) — структура, где добавлять и удалять можно с обоих концов за константное время.

Проблема, которую он решает

В Python список выглядит универсальным. Но у него есть узкое место: операции в начале.

queue = [1, 2, 3, 4, 5]
queue.pop(0)      # O(n) — все элементы сдвигаются влево
queue.insert(0, 0) # O(n) — все элементы сдвигаются вправо

Список хранит элементы непрерывно, поэтому удаление первого требует сдвинуть все остальные. На очереди из 100 000 элементов обработка выродится в 5 миллиардов операций.

Дек устроен иначе — как двусвязный список блоков. У него есть указатели на оба конца, и добавление или удаление там не трогает остальные элементы.

Использование в Python

from collections import deque

d = deque([1, 2, 3])

d.append(4)        # справа:  [1, 2, 3, 4]
d.appendleft(0)    # слева:   [0, 1, 2, 3, 4]

d.pop()            # 4, справа
d.popleft()        # 0, слева

print(d)           # deque([1, 2, 3])

Полезные дополнительные операции:

d = deque([1, 2, 3, 4, 5])

d.rotate(2)        # сдвиг вправо: deque([4, 5, 1, 2, 3])
d.rotate(-1)       # сдвиг влево

d.extendleft([0, -1])  # ВНИМАНИЕ: добавляет в обратном порядке
                       # получится [-1, 0, 4, 5, 1, 2, 3]

extendleft переворачивает порядок — это логично, ведь каждый элемент добавляется слева, но интуиции противоречит и регулярно ловит новичков.

Дек с ограниченной длиной

Очень удобная возможность: при переполнении лишние элементы автоматически выталкиваются с противоположного конца.

last_five = deque(maxlen=5)

for i in range(10):
    last_five.append(i)

print(last_five)   # deque([5, 6, 7, 8, 9], maxlen=5)

Готовая структура для «последних N событий»: скользящий лог, история команд, последние сообщения. Никакой ручной обрезки.

Три задачи, где дек незаменим

Очередь для BFS

Обход графа в ширину — самое частое применение. Элементы добавляются в конец, извлекаются из начала.

from collections import deque


def bfs(graph: dict, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()      # O(1), со списком было бы O(n)
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
print(bfs(graph, 1))   # [1, 2, 3, 4]

Замена deque на list здесь превращает O(V + E) в O(V² + E). На больших графах разница катастрофическая.

Максимум в скользящем окне

Классическая задача: для каждого окна длины k найти максимум. Наивно — O(n·k). С деком — O(n).

В деке храним индексы, поддерживая значения по убыванию.

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq = deque()      # индексы, значения по убыванию
    result = []

    for i, num in enumerate(nums):
        # выбрасываем индексы, вышедшие за окно
        while dq and dq[0] <= i - k:
            dq.popleft()

        # выбрасываем всех, кто меньше текущего — они уже не станут максимумом
        while dq and nums[dq[-1]] < num:
            dq.pop()

        dq.append(i)

        if i >= k - 1:
            result.append(nums[dq[0]])   # максимум всегда слева

    return result


print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Здесь нужны операции с обоих концов одновременно: слева убираем устаревшее, справа — ставшее ненужным. Ни стек, ни очередь по отдельности не подойдут.

Проверка палиндрома

Сравниваем символы с двух концов, сходясь к середине.

def is_palindrome(s: str) -> bool:
    d = deque(c.lower() for c in s if c.isalnum())

    while len(d) > 1:
        if d.popleft() != d.pop():
            return False

    return True


print(is_palindrome('А роза упала на лапу Азора'))  # True

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Как он устроен внутри

Реализация в CPython — не классический двусвязный список из отдельных узлов, а список блоков. Каждый блок содержит 64 элемента, блоки связаны указателями.

[блок 1: 64 эл.] ⇄ [блок 2: 64 эл.] ⇄ [блок 3: 64 эл.]
       ↑                                        ↑
     левый конец                          правый конец

Это компромисс между списком и массивом: указателей в 64 раза меньше, чем при поузловой организации, а локальность памяти внутри блока хорошая. Отсюда и приличная скорость обхода, хотя доступ по произвольному индексу всё равно O(n) — нужно пройти по блокам.

Когда дек не нужен

Нужен доступ по индексу. d[500] работает за O(n). Если вы часто обращаетесь к середине, берите список.

Только стек. Если добавление и удаление идут исключительно с одного конца, обычный список справится не хуже: append и pop у него O(1).

Нужны срезы. Дек их не поддерживает: d[1:3] вызовет TypeError.

Аналоги в других языках

В JavaScript отсутствие дека — известная проблема. Array.shift() работает за O(n), и для очередей на больших данных приходится писать кольцевой буфер вручную или держать два указателя на массив.

Частые ошибки

Использование списка как очереди. Самая частая и самая дорогая. list.pop(0) в цикле — скрытый квадрат.

Ожидание прямого порядка от extendleft. Порядок переворачивается.

Обращение по индексу в цикле. for i in range(len(d)): d[i] даёт O(n²). Итерируйтесь напрямую: for x in d.

Попытка сделать срез. Не поддерживается; используйте itertools.islice.

Что запомнить

• Дек даёт O(1) на добавление и удаление с обоих концов.
• В Python это collections.deque; для очереди всегда предпочитайте его списку.
• maxlen даёт готовое окно последних N элементов.
• Незаменим для BFS и для задач на скользящее окно, где нужны оба конца.
• Доступ по индексу O(n) и срезы не поддерживаются — за этим к списку.