Модуль 20 ⏱ ~22 мин чтения 📐 4 Mermaid диаграмм

6. Дек - двусторонняя очередь

Дек: симметрия двусторонней очереди и алгоритм Work Stealing

В предыдущих статьях мы детально препарировали две фундаментальные абстракции: 4. Стек с его строгим принципом LIFO («последним пришел — первым ушел») и 5. Очередь с ее справедливой моделью FIFO («первым пришел — первым ушел»). Но архитектура реальных высокопроизводительных сервисов, рантаймов и планировщиков задач часто требует универсальных гибридных подходов.

Что делать, если системе требуется обрабатывать входящие события в порядке очереди (FIFO), но в случае сбоя или временной недоступности внешней базы данных необходимо вернуть задачу обратно в самое начало очереди без потери приоритета? Или как реализовать распределенный планировщик вычислений, где свободные процессорные ядра могут безопасно «красть» задачи у перегруженных соседей?

Для таких задач применяется Дек (Deque — Double-Ended Queue, двусторонняя очередь).

Архитектура Дека

Дек снимает односторонние ограничения стека и очереди, предоставляя симметричную возможность добавлять и извлекать элементы с обоих концов за константное время $O(1)$.

Контракт двусторонней очереди базируется на четырех ключевых операциях:

PushFront — добавить элемент в начало (Голову / Head).
PushBack — добавить элемент в конец (Хвост / Tail).
PopFront — извлечь элемент из начала.
PopBack — извлечь элемент из конца.

flowchart LR
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    PushFront["PushFront<br/>Вставка в голову"]:::process --> Head["Head (Голова)"]
    Head --> PopFront["PopFront<br/>Извлечение из головы"]

    Head --- E1["Элемент 1"] --- E2["Элемент 2"] --- E3["Элемент 3"] --- Tail["Tail (Хвост)"]

    PushBack["PushBack<br/>Вставка в хвост"] --> Tail
    Tail --> PopBack["PopBack<br/>Извлечение из хвоста"]

Mechanical Sympathy: Проблема наивной реализации

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

Если мы попытаемся сделать PushFront через встроенный append в Go:

// ХУДШИЙ КОД ДЛЯ ПРОДАКШЕНА
deque := []int{1, 2, 3}
deque = append([]int{0}, deque...) // PushFront

Для вставки одного элемента рантайму Go придется:

Аллоцировать новый базовый массив.
Скопировать туда 0.
Скопировать весь старый deque (O(N) операция).
Оставить старый массив на растерзание Garbage Collector-у.

На 100 000 элементов эта операция поставит ваш бэкенд на колени из-за деградации кэша CPU и гигантского GC Churn.

Выбор базы для Дека

У нас есть два пути для создания эффективного дека:

Двусвязный список (Doubly Linked List): У каждого узла есть next и prev. $O(1)$ на все операции. Но, как мы разбирали в 3. Связные списки, это сопровождается промахами кэша (Cache Misses) из-за случайного доступа к памяти (Pointer Chasing).
Динамический кольцевой буфер (Dynamic Ring Buffer): Мы используем непрерывный слайс, но "замыкаем" его концы в кольцо. Указатели head и tail бегают по кругу. Когда места не хватает, мы создаем новый слайс в 2 раза больше и "разворачиваем" старое кольцо в прямую линию. Это дает амортизированное $O(1)$ и идеальный Cache Locality.

Стандартом в высокопроизводительной инженерии является именно второй вариант.

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    subgraph RingBufferState["Динамический кольцевой буфер в срезе"]
        direction LR
        b0["buf[0] = C (tail)"] --- b1["buf[1] = free"] --- b2["buf[2] = free"] --- b3["buf[3] = A (head)"] --- b4["buf[4] = B"]
    end
    HeadPtr["Head = 3"] --> b3
    TailPtr["Tail = 0"] --> b0

Production-Ready реализация на Go

Ниже представлена реализация быстрого, безопасного для памяти (без утечек) Дека на основе кольцевого буфера с использованием дженериков.

package main

import "errors"

var ErrDequeEmpty = errors.New("deque is empty")

// Deque реализует двустороннюю очередь поверх закольцованного слайса.
type Deque[T any] struct {
    buf  []T
    head int
    tail int
    size int
}

func NewDeque[T any](initialCapacity int) *Deque[T] {
    if initialCapacity < 2 {
        initialCapacity = 2
    }
    return &Deque[T]{
        buf: make([]T, initialCapacity),
    }
}

// PushBack добавляет элемент в конец (как в обычную очередь/стек)
func (d *Deque[T]) PushBack(val T) {
    if d.size == len(d.buf) {
        d.grow()
    }
    d.buf[d.tail] = val
    // Сдвигаем хвост по кольцу
    d.tail = (d.tail + 1) % len(d.buf)
    d.size++
}

// PushFront добавляет элемент в начало
func (d *Deque[T]) PushFront(val T) {
    if d.size == len(d.buf) {
        d.grow()
    }
    // Сдвигаем голову по кольцу влево (с учетом перехода через 0)
    d.head = (d.head - 1 + len(d.buf)) % len(d.buf)
    d.buf[d.head] = val
    d.size++
}

// PopFront извлекает элемент из начала
func (d *Deque[T]) PopFront() (T, error) {
    var zero T
    if d.size == 0 {
        return zero, ErrDequeEmpty
    }

    val := d.buf[d.head]
    d.buf[d.head] = zero // Избегаем утечек памяти (GC Leak)

    d.head = (d.head + 1) % len(d.buf)
    d.size--
    return val, nil
}

// PopBack извлекает элемент из конца
func (d *Deque[T]) PopBack() (T, error) {
    var zero T
    if d.size == 0 {
        return zero, ErrDequeEmpty
    }

    // Сдвигаем хвост влево
    d.tail = (d.tail - 1 + len(d.buf)) % len(d.buf)
    val := d.buf[d.tail]
    d.buf[d.tail] = zero // Избегаем утечек памяти

    d.size--
    return val, nil
}

// grow удваивает capacity и "выпрямляет" кольцо
func (d *Deque[T]) grow() {
    newCap := len(d.buf) * 2
    newBuf := make([]T, newCap)

    // Если кольцо разорвано (tail находится до head), 
    // нужно аккуратно скопировать две части
    if d.tail <= d.head {
        // Копируем от head до конца старого массива
        copy(newBuf, d.buf[d.head:])
        // Копируем от начала старого массива до tail
        copy(newBuf[len(d.buf)-d.head:], d.buf[:d.tail])
    } else {
        // Кольцо не разорвано, просто копируем
        copy(newBuf, d.buf[d.head:d.tail])
    }

    d.buf = newBuf
    d.head = 0
    d.tail = d.size
}

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    subgraph RingGrow["Развертывание разорванного кольца при grow()"]
        direction TB
        OldRing["Старый буфер (tail <= head): [0..tail-1] и [head..len-1]"]
        NewLinear["Новый удвоенный буфер:<br/>[head..len-1] скопировано в начало<br/>[0..tail-1] пристыковано следом<br/>head сброшен в 0, tail = size"]
    end
    OldRing -->|"copy() в два шага"| NewLinear

Собеседование (Хардкорная оптимизация)

Вопрос: Оператор остатка от деления % работает относительно медленно на уровне процессора (требует десятков тактов). Как ускорить кольцевой буфер?

Ответ: Мы можем принудительно сделать размер буфера (capacity) степенью двойки (2, 4, 8, 16...). Тогда медленный оператор % len можно заменить на сверхбыструю побитовую операцию И (&).
Выражение (head + 1) % 16 абсолютно идентично (head + 1) & 15.
Побитовое И выполняется процессором за 1 такт. Это классический прием (Mechanical Sympathy), который используется в исходниках Go и Linux-ядра для кольцевых структур.

Где реально используется Дек? Паттерн Work Stealing

Вы можете спросить: "А зачем в реальном бэкенде нужна структура, в которую можно пихать данные с двух сторон?".

Ответ кроется в алгоритме Work Stealing (Кража работы), на котором базируется планировщик горутин в Go (а также пулы потоков в Java ForkJoinPool и Tokio в Rust).

Представьте, что у нас есть несколько рабочих потоков (тредов процессора). У каждого потока есть своя локальная очередь задач.

Локальный поток добавляет новые горутины и берет их на выполнение со своего конца дека (например, с хвоста). Для него дек работает как Стек (LIFO). Это максимизирует Cache Locality: свежесозданная задача, скорее всего, всё ещё находится в L1 кэше процессора.
Но что если один поток закончил все свои задачи, а другой завален работой?
Свободный поток становится "Вором" (Thief). Он идет к загруженному потоку и крадет задачи с противоположного конца дека (с головы). Для вора дек работает как Очередь (FIFO).

flowchart TD
    classDef process  fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success  fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error    fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning  fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry    fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef aux      fill:#334155,stroke:#64748b,stroke-width:1px,color:#f8fafc
    classDef system   fill:#312e81,stroke:#a78bfa,stroke-width:1px,color:#f8fafc
    classDef data     fill:#132d29,stroke:#2dd4bf,stroke-width:1px,color:#f8fafc
    classDef network  fill:#881337,stroke:#fb7185,stroke-width:1px,color:#f8fafc
    classDef accent   fill:#1e1b4b,stroke:#818cf8,stroke-width:1px,color:#f8fafc
    subgraph DequeLayout["Дек загруженного потока (P)"]
        Head["Голова<br/>(Старые задачи)"] --- Middle["..."] --- Tail["Хвост<br/>(Свежие задачи)"]
    end

    Owner["Владелец потока (P/M)"]
    Thief["Свободный поток (Вор)"]

    %% Владелец работает с хвостом в обе стороны (как Стек LIFO)
    Owner -->|"PushBack (кладет задачу)"| Tail
    Tail -->|"PopBack (берет задачу)"| Owner

    %% Вор работает с головой только на извлечение (как Очередь FIFO)
    Head -->|"PopFront (крадет задачу)"| Thief

Почему вор берет задачи с головы? Потому что там лежат самые старые задачи (возможно, тяжелые или создавшие целое поддерево новых горутин). Украв старую задачу, вор надолго обеспечит себя работой, снизив необходимость постоянно блокировать чужой дек. Дек делает этот элегантный алгоритм возможным.

Итог

Дек (Double-Ended Queue) — это универсальная структура, объединяющая возможности стека и очереди.
Наивная реализация на срезах слайсов (append с перераспределением) недопустима из-за сложности O(N).
Продакшен-решения используют Кольцевой буфер (Ring Buffer), который разворачивается (реаллоцируется) только при полном заполнении, обеспечивая амортизированное $O(1)$ и прекрасную работу с кэшем CPU.
Дек является ключевой структурой для алгоритмов балансировки нагрузки, таких как Work Stealing.

В этой статье мы реализовали дек на базе концепции "кольцевого буфера". В следующей статье мы окончательно препарируем эту концепцию. Мы разберем, как кольцевой буфер работает в условиях жестких ограничений по памяти (без динамического расширения) и почему он является ядром сетевого программирования (I/O) и каналов в Go: 7. Кольцевой буфер.