Дек

Что такое дек

Дек (deque, от double-ended queue) — двусторонняя очередь: добавлять и забирать элементы можно с обоих концов. В отличие от очереди (только FIFO) и стека (только LIFO), дек объединяет обе возможности.

Четыре операции:

Стек и очередь — частные случаи дека:

• пользуемся только push_back и pop_back — получаем стек (LIFO);
• пользуемся только push_back и pop_front — получаем очередь (FIFO).

Плата за универсальность — два указателя в каждом узле (на предыдущий и следующий), то есть двусвязный список.

Реализация на двусвязном списке

#include <stdio.h>
#include <stdlib.h>

typedef struct DequeNode
{
    int value;                 /* полезные данные */
    struct DequeNode *prev;    /* предыдущий узел, NULL у головы */
    struct DequeNode *next;    /* следующий узел, NULL у хвоста */
} DequeNode;

typedef struct
{
    DequeNode *head;           /* первый узел */
    DequeNode *tail;           /* последний узел */
} Deque;

Инварианты дека.

1. head == NULL <=> tail == NULL — дек либо пуст, либо у него есть оба конца.
2. У головы prev == NULL, у хвоста next == NULL.
3. Для любых соседних узлов a и b (где b следует за a): a->next == b и b->prev == a — ссылки смотрят друг на друга.

Если инвариант 3 нарушен (например, забыли обновить prev), то одна из операций на противоположном конце найдёт «дыру» и дек разорвётся.

Создание узла и вспомогательные функции

/* Создать узел с заданным значением */
DequeNode *make_node(int value)
{
    DequeNode *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return NULL;
    }

    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

/* Инициализация пустого дека */
void deque_init(Deque *d)
{
    d->head = NULL;
    d->tail = NULL;
}

/* Пуст ли дек? */
int deque_is_empty(const Deque *d)
{
    return d->head == NULL;
}

/* Освободить все узлы */
void free_deque(Deque *d)
{
    DequeNode *p = d->head;
    while (p != NULL)
    {
        DequeNode *next = p->next;   /* сохраняем до free */
        free(p);
        p = next;
    }
    d->head = NULL;
    d->tail = NULL;
}

push_front

Добавляем новый узел перед текущей головой:

int push_front(Deque *d, int value)
{
    DequeNode *node = make_node(value);
    if (node == NULL)
    {
        return 0;
    }

    if (d->head == NULL)
    {
        d->head = node;        /* дек был пуст — узел и голова, и хвост */
        d->tail = node;
    }
    else
    {
        node->next = d->head;  /* новый узел ссылается на старую голову */
        d->head->prev = node;  /* старая голова ссылается назад */
        d->head = node;        /* новый узел становится головой */
    }
    return 1;
}

Обратите внимание на порядок в ветке else. Три присваивания:

1. node->next = d->head — прицепляемся к старой голове.
2. d->head->prev = node — замыкаем обратную ссылку.
3. d->head = node — переставляем голову.

Если поменять местами пункты 1 и 3 (сначала d->head = node, потом node->next), то старая голова потеряется, и связать новый узел со списком будет нечем.

push_back

Зеркально push_front:

int push_back(Deque *d, int value)
{
    DequeNode *node = make_node(value);
    if (node == NULL)
    {
        return 0;
    }

    if (d->tail == NULL)
    {
        d->head = node;
        d->tail = node;
    }
    else
    {
        node->prev = d->tail;  /* новый узел ссылается назад на старый хвост */
        d->tail->next = node;  /* старый хвост ссылается вперёд */
        d->tail = node;        /* новый узел становится хвостом */
    }
    return 1;
}

pop_front

int pop_front(Deque *d, int *out)
{
    if (d->head == NULL)
    {
        return 0;              /* дек пуст */
    }

    DequeNode *node = d->head;
    *out = node->value;

    d->head = node->next;      /* головой становится следующий */
    if (d->head == NULL)
    {
        d->tail = NULL;        /* забрали последний узел */
    }
    else
    {
        d->head->prev = NULL;  /* у новой головы не должно быть prev */
    }

    free(node);
    return 1;
}

Ключевой момент — строка d->head->prev = NULL. Если после удаления в деке остались элементы, у новой головы prev всё ещё указывает на освобождённый узел. Не обнулили — нарушен инвариант 2, и будущий pop_back пойдёт по висячему указателю.

pop_back

int pop_back(Deque *d, int *out)
{
    if (d->tail == NULL)
    {
        return 0;
    }

    DequeNode *node = d->tail;
    *out = node->value;

    d->tail = node->prev;      /* хвостом становится предыдущий */
    if (d->tail == NULL)
    {
        d->head = NULL;        /* забрали последний узел */
    }
    else
    {
        d->tail->next = NULL;  /* у нового хвоста не должно быть next */
    }

    free(node);
    return 1;
}

Пошагово: какие указатели меняются

Соберём всё в одну таблицу. Пусть «есть» означает, что в деке ещё остались элементы после операции; «пусто» — что операция убрала последний.

Из таблицы видно правило: любое удаление, после которого дек остаётся непустым, обязано закрыть «оборванную» ссылку — prev у новой головы или next у нового хвоста. Иначе инвариант 3 нарушается.

Удаление последнего элемента

Когда в деке один узел, head == tail == node, а node->prev == node->next == NULL. pop_front ставит head = node->next (то есть NULL), затем заходит в ветку if (d->head == NULL) и обнуляет tail. Без этого tail указывал бы на освобождённый узел, и следующий push_back записал бы в освобождённую память. pop_back симметрично обнуляет head. В обоих случаях после удаления последнего оба указателя — NULL, инвариант 1 восстановлен.

Сравнение с очередью и стеком

• Стек — один конец, достаточно head; операции push/pop трогают только голову.
• Очередь — два конца (head и tail), но однонаправленное движение: добавили в конец, забрали из начала. Достаточно односвязного списка.
• Дек — два конца и движение в обе стороны. Нужен двусвязный список: чтобы удалить хвост за O(1), надо знать его prev, а в односвязном списке это потребовало бы полного обхода.

Именно вторая ссылка (prev) — то, что «покупает» дек за счёт лишней памяти в каждом узле.

Дек на массиве (кольцевой буфер)

Как и очередь, дек можно построить на массиве фиксированного размера с двумя индексами, движущимися по кругу. push_front уменьшает левый индекс, push_back увеличивает правый; при достижении границы индексы «перескакивают» на противоположный край.

Плюсы и минусы те же, что у очереди на кольцевом буфере:

• плюс — непрерывная память, нет накладных расходов на prev/next и malloc на узел;
• минус — фиксированный размер, отдельная логика для пустого/заполненного дека и «переполнения».

На списке же дек растёт динамически, а все четыре операции честно O(1).

Где применяется дек

• Скользящее окно — нужно быстро добавлять элемент справа и убирать устаревший слева; дек идеально подходит для хранения «текущего окна» (например, поиск минимума в каждом окне длины K).
• Двусторонняя буферизация — буфер, в который данные приходят с двух сторон или забираются с двух сторон.
• Undo/redo — историю действий можно хранить в деке: откат берёт последний элемент (pop_back), а при нехватке места вытесняют самый старый (pop_front).

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

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

1. Дек — очередь с обоих концов: четыре операции, все O(1).
2. Стек и очередь — частные случаи дека.
3. Дек строится на двусвязном списке: prev и next в каждом узле.
4. Инварианты: head == NULL <=> tail == NULL; у головы prev == NULL, у хвоста next == NULL; соседние ссылки смотрят друг на друга.
5. При удалении не последнего элемента закрывайте «оборванную» ссылку (prev или next).
6. При удалении последнего элемента обнуляйте оба указателя.
7. Порядок присваиваний при вставке: сначала связать узел, потом переставить конец.

Связь с ЛР 3

Дек не входит в варианты лабораторной №3. Но его основа — двусвязный список — это ровно та структура, которая используется в повышенных вариантах (П1–П5). Освоив push_front/push_back/pop_front/pop_back, вы свободно напишете вставку и удаление в любом месте двусвязного списка Student, не теряя ни prev, ни next, ни границы head/tail.

Документация

• malloc
• free
• Структуры
• Указатели