Очередь

Что такое очередь

Очередь работает по принципу FIFO — first in, first out: «первый пришёл — первый ушёл». Кто встал в очередь раньше, тот раньше из неё и выйдет.

Аналогия. Очередь в столовой: новые люди пристраиваются в конец, а раздача всегда обслуживает того, кто стоит в начале. Никто не «протискивается» в середину.

У очереди два конца, и они разные по смыслу:

• head — начало очереди, откуда забирают элементы;
• tail — конец очереди, куда добавляют новые элементы.

Операции очереди:

Ключевое требование к очереди — обе «рабочие» операции, enqueue и dequeue, должны выполняться за константное время. Достигается это хранением сразу двух указателей: не приходится каждый раз пробегать весь список, чтобы найти конец.

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

Возьмём односвязный узел и структуру, хранящую оба конца:

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

typedef struct QueueNode
{
    int value;               /* полезные данные */
    struct QueueNode *next;  /* адрес следующего узла, NULL — конец */
} QueueNode;

typedef struct
{
    QueueNode *head;         /* начало: откуда забираем */
    QueueNode *tail;         /* конец: куда добавляем */
} Queue;

Инвариант очереди. Либо очередь пуста и оба указателя равны NULL, либо она непуста и оба указывают на настоящие узлы. Формально:

head == NULL  <=>  tail == NULL

Это правило должно выполняться до и после каждой операции. Если head != NULL, а tail == NULL (или наоборот) — очередь «порвана», и одна из операций рано или поздно разыменует NULL.

Соберём очередь целиком:

/* Инициализация пустой очереди */
void queue_init(Queue *q)
{
    q->head = NULL;
    q->tail = NULL;
}

/* Пуста ли очередь? */
int queue_is_empty(const Queue *q)
{
    return q->head == NULL;
}

/* Добавить элемент в конец */
int enqueue(Queue *q, int value)
{
    QueueNode *node = malloc(sizeof(*node));
    if (node == NULL)
    {
        return 0;              /* память не выделилась */
    }

    node->value = value;
    node->next = NULL;

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

/* Забрать элемент из начала */
int dequeue(Queue *q, int *out)
{
    if (q->head == NULL)
    {
        return 0;              /* очередь пуста */
    }

    QueueNode *node = q->head;
    *out = node->value;

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

    free(node);
    return 1;
}

/* Посмотреть начало, не удаляя */
int queue_front(const Queue *q, int *out)
{
    if (q->head == NULL)
    {
        return 0;
    }

    *out = q->head->value;
    return 1;
}

/* Освободить все оставшиеся узлы */
void free_queue(Queue *q)
{
    QueueNode *p = q->head;
    while (p != NULL)
    {
        QueueNode *next = p->next;   /* СНАЧАЛА запоминаем следующий */
        free(p);
        p = next;
    }
    q->head = NULL;
    q->tail = NULL;
}

Обратите внимание на два места.

1. Проверка malloc. Если памяти не хватило, enqueue возвращает 0 и очередь не меняется — вызывающий код обязан проверить результат и обработать ошибку.
2. Проверка пустоты в dequeue. Разбирать пустую очередь нельзя: q->head->value при q->head == NULL — разыменование нулевого указателя.

Порядок действий в enqueue и dequeue

enqueue в пустую очередь

Создали узел node. Очередь пуста, head == tail == NULL. Узел одновременно становится и головой, и хвостом:

if (q->tail == NULL)
{
    q->head = node;
    q->tail = node;
}

Если забыть присвоить q->head, то голова так и останется NULL: dequeue будет считать очередь пустой, хотя tail уже указывает на узел — нарушен инвариант, и узел «зависает» (плюс утечка, потому что free_queue обходит от head и до него не дойдёт).

enqueue в непустую очередь

Есть хвост tail. Присоединяем новый узел за ним и двигаем хвост:

q->tail->next = node;  /* старый хвост теперь ссылается на новый узел */
q->tail = node;        /* новый узел становится хвостом */

Порядок обязателен именно такой. Если сначала написать q->tail = node, то старый хвост потерян, и прицепить новый узел к цепочке уже нечем — очередь разорвётся, а все прежние элементы окажутся недостижимы.

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

В очереди один узел: head == tail == node, а node->next == NULL. Выполняем:

QueueNode *node = q->head;
*out = node->value;
q->head = node->next;   /* q->head == NULL */
if (q->head == NULL)
{
    q->tail = NULL;     /* обнуляем хвост */
}
free(node);

Строка q->tail = NULL — самая важная здесь. Без неё после удаления последнего элемента head == NULL, но tail продолжает указывать на уже освобождённый узел. Следующий enqueue пойдёт по ветке q->tail != NULL и запишет в q->tail->next — то есть в освобождённую память. Это неопределённое поведение: программа может «работать», а может рухнуть позже в случайном месте.

Почему нельзя двигать head, не сохранив next

В dequeue мы сначала запоминаем узел и его next, и только потом освобождаем. Если сделать наоборот:

free(q->head);          /* освободили узел */
q->head = q->head->next;/* читаем поле уже освобождённого узла — ошибка! */

то обращение к q->head->next происходит уже после free — обращение к освобождённой памяти. Порядок «сначала сохрани next, потом освободи» убирает эту ошибку.

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

Очередь можно построить не только на списке, но и на массиве фиксированного размера с двумя индексами front и rear. Это кольцевой буфер: когда rear доходит до конца массива, он «перескакивает» в начало, если там есть свободное место.

Зачем это нужно: массив лежит в памяти непрерывно, доступ к элементу по индексу мгновенный, нет накладных расходов на указатели и malloc под каждый узел. Минусы тоже есть:

• размер фиксирован заранее — очередь может «переполниться»;
• нужно отдельно различать пустую очередь и заполненную до отказа (например, хранить счётчик элементов или резервировать одну «лишнюю» ячейку);
• при заполнении массив приходится либо увеличивать (копировать), либо отбрасывать новые элементы.

Для лабораторной №3, где данные читаются из файла и число записей заранее неизвестно, список удобнее: не нужно гадать с размером буфера.

Где применяется очередь

• Обход в ширину (BFS) — очередь хранит вершины графа, которые предстоит обработать; порядок FIFO и есть порядок обхода по уровням.
• Буферы — например, очередь пакетов между производителем и потребителем: приходит пакет — в конец, обрабатывается — из начала.
• Обработка заявок — сервер, магазин, кол-центр: заявки обслуживаются в порядке поступления.
• Планировщик — задачи, ожидающие CPU, выстраиваются в очередь готовых процессов.

Общая черта всех применений: важен порядок поступления, и ни один элемент не должен обслуживаться «вне очереди».

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

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

1. Очередь — FIFO: добавляем в конец (tail), забираем из начала (head).
2. Инвариант: head == NULL тогда и только тогда, когда tail == NULL.
3. enqueue и dequeue — O(1), потому что храним оба указателя.
4. При удалении последнего элемента обязательно обнуляйте tail.
5. Перед free узла сохраняйте его next.
6. Проверяйте пустоту в dequeue и результат malloc в enqueue.
7. После работы освобождайте все узлы и обнуляйте оба указателя.

Связь с ЛР 3

Очередь не входит в варианты лабораторной №3 — ни в основные (1–20), ни в повышенные (П1–П5), ни в высокие (В1–В5). Этот раздел полезен как тренажёр по работе с указателями: здесь в одном месте встречаются добавление в конец, удаление из начала, обнуление tail и освобождение памяти — ровно те приёмы, которые понадобятся при реализации односвязного списка Student из основных вариантов.

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

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