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

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

В чем проблема

Со стеком на массиве все было просто: оба действия происходят с одного конца, элементы накапливаются и убывают у одной границы. У очереди концы разные: добавляем справа, забираем слева. Занятый участок массива постепенно смещается вправо - и рано или поздно упирается в конец, хотя в начале массива полно свободного места.

Три стратегии

1. Сдвиг при каждом извлечении. Голова всегда в ячейке 0; после Dequeue все оставшиеся элементы сдвигаются на позицию влево. Извлечение дорожает до O(N) - в учебнике эта стратегия иронично названа стратегией "трудоголика".
2. "Ленивая" стратегия. Голова и хвост движутся вправо; когда хвост упирается в конец массива, вся очередь разом копируется в начало. В среднем быстро, но изредка случаются задержки O(N).
3. Кольцевой буфер - оптимальная стратегия. Массив мысленно замыкается в кольцо: дойдя до конца, индекс перескакивает на 0, где место уже освободили ушедшие элементы. Никаких перемещений данных, обе операции - O(1).

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

Структура хранит массив, индекс головы first и количество элементов size. "Замыкание" массива дает операция остатка от деления:

• индекс хвоста (первой свободной ячейки) = (first + size) % POOL_SIZE;
• Dequeue сдвигает голову по кольцу: first = (first + 1) % POOL_SIZE.

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

#include <stdbool.h>

#define POOL_SIZE 100

typedef struct {
    int first;           /* индекс головы (откуда берем) */
    int size;            /* текущее количество элементов */
    int data[POOL_SIZE]; /* статический массив */
} Queue;

void Create(Queue* q) {
    q->first = 0;
    q->size = 0;
}

/* Добавление: хвост вычисляется через остаток от деления */
bool Push(Queue* q, int val) {
    if (q->size == POOL_SIZE) return false; /* буфер полон */

    q->data[(q->first + q->size) % POOL_SIZE] = val;
    q->size++;
    return true;
}

/* Извлечение: голова сдвигается по кольцу */
bool Pop(Queue* q) {
    if (q->size == 0) return false; /* очередь пуста */

    q->first = (q->first + 1) % POOL_SIZE;
    q->size--;
    return true;
}

Плата та же, что у стека на массиве: размер зафиксирован, при size == POOL_SIZE наступает переполнение. Как снять этот лимит - в следующем уроке.