Очередь. Логическое описание и физическое представление (динамические объекты): два указателя

Модуль "Очередь и дек" • урок 4 из 7 • ~7 минут

Что это такое

Как и стек на связном списке, динамическая очередь строится из узлов в куче: узел = данные + указатель next на следующий узел. Память выделяется под каждый элемент отдельно (malloc) и возвращается при извлечении (free).

Зачем это нужно

Кольцевой буфер из прошлого урока быстр, но ограничен размером POOL_SIZE: при переполнении - отказ. Динамическая очередь ограничена только объемом оперативной памяти: она растет и сжимается по мере надобности, не резервируя лишнего.

Очередь. Логическое описание и физическое представление (динамические объекты): почему указателей два

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

• first - голова, отсюда извлекает Dequeue;
• last - хвост, сюда добавляет Enqueue.

Если хранить только голову, то для добавления в конец пришлось бы каждый раз проходить всю цепочку в поисках последнего узла - это O(N). Указатель last сводит вставку к O(1).

Еще один прием - пустой служебный узел, терминатор: на него изначально указывают и first, и last. Он избавляет код Enqueue и Dequeue от отдельных проверок "а не пуста ли очередь" при работе с указателями: цепочка никогда не бывает совсем пустой.

Реализация на C

#include <stdlib.h>

/* Узел очереди (рекурсивная структура) */
typedef struct Item {
    int data;
    struct Item* next; /* указатель на следующий узел */
} Item;

/* Очередь: два указателя и счетчик */
typedef struct {
    Item* first; /* голова: откуда берем */
    Item* last;  /* хвост: куда кладем */
    int size;    /* длина за O(1) */
} Queue;

/* Создание с узлом-терминатором */
void Create(Queue* q) {
    Item* terminator = (Item*)malloc(sizeof(Item));
    terminator->next = NULL;
    q->first = terminator;
    q->last = terminator;
    q->size = 0;
}

/* Добавление в хвост - O(1) */
void Push(Queue* q, int val) {
    Item* newItem = (Item*)malloc(sizeof(Item));
    newItem->next = NULL;      /* новый узел станет терминатором */

    q->last->data = val;       /* старый терминатор принимает данные */
    q->last->next = newItem;

    q->last = newItem;         /* хвост сдвигается */
    q->size++;
}

/* Извлечение из головы - O(1) */
int Pop(Queue* q) {
    Item* t = q->first;
    int val = t->data;
    q->first = t->next;        /* голова сдвигается */
    free(t);
    q->size--;
    return val;
}

Обратите внимание на трюк с терминатором в Push: новый узел создается пустым, а данные записываются в прежний терминатор. Так вставка не требует проверять, пуста ли очередь.

Массив или список

• Кольцевой буфер: быстрее на практике (сплошная память, без malloc), но размер фиксирован. Выбор для буферов известного размера - клавиатура, сеть.
• Связный список: нет лимита, но malloc/free на каждую операцию и память под указатели. Выбор, когда длина очереди непредсказуема.