Кольцевая очередь (Circular Queue): анимация

Визуализация

Сценарий: Заворот через конец

Сценарий:

Вместимость кольца: 6 ячеек, размер зафиксирован при создании. Ползунок задает, сколько операций проигрывается, а не размер массива.

Легенда цветов

элемент в очереди текущая операция запись значения чтение значения

Элементов 3

Нажмите "Пуск" или листайте по шагам.

Заполнено: 0 / 6 Операций: 0 Шаг: 0 / 0 Сложность по времени: -

Как работает кольцевая очередь

Идея структуры: Обычная очередь на массиве страдает от проблемы "уползания" данных - при удалении элементов из начала массива остаются пустые ячейки, которые нельзя переиспользовать, если хвост уже достиг конца. Кольцевая очередь (Circular Queue) решает эту проблему элегантным математическим трюком - заворотом индексов через операцию деления по модулю.

Кольцевая очередь: хвост доходит до конца массива и заворачивается в начало по остатку от деления, голова идет следом (Circular Queue)

Ключевые механизмы:

Заворот хвоста и головы: Вместо простого инкремента i = i + 1 используется формула с остатком от деления i = (i + 1) mod CAPACITY. Это позволяет индексу, дошедшему до конца массива, "перепрыгнуть" на нулевую позицию, тем самым замыкая массив в логическое кольцо.
Фиксированная вместимость: Кольцевой буфер работает в рамках заранее выделенного массива размером CAPACITY. Если count == CAPACITY, очередь считается переполненной, и дальнейшие вставки игнорируются (или затирают старые данные, в зависимости от задачи).

Сфера применения: Эта структура идеальна для систем реального времени и поточной обработки, где память ограничена и не должна перевыделяться. Типичные примеры: аудио и видео буферы, сетевые пакеты в маршрутизаторах, планировщики задач в ОС (CPU scheduling), буферизация ввода-вывода (например, буфер клавиатуры).

Откуда взялась проблема. Посмотрите сценарий "Поток" в анимации обычной очереди: там оба указателя уходят вправо и оставляют за собой пустую память, которую уже не вернуть. Кольцевая очередь - ответ ровно на это.

Синонимы названия: Кольцевой буфер, Циклический буфер, Ring Buffer, Circular Queue.

Сложность

Сложность - это оценка того, как быстро растет потребление ресурса при росте числа элементов n. Ресурса у структуры два, поэтому и оценки две: по времени и по памяти. Обе записывают через O-нотацию - у нас есть отдельная анимация о том, как читать такие записи.

Кольцевая очередь - это одна из самых быстрых и стабильных структур данных. Никакие операции не вызывают сдвиг массива или перевыделение памяти.

По времени

Операция	Время	Комментарий
Вставка (enqueue)	O(1)	Элемент записывается в хвост, индекс вычисляется арифметически.
Извлечение (dequeue)	O(1)	Элемент читается с головы, индекс смещается за один шаг.
Доступ (peek/front)	O(1)	Прямое обращение по индексу `head`.

По памяти

Характеристика	Оценка	Комментарий
Затраты памяти	O(K)	Выделяется фиксированный массив размером `K` (вместимость). Дополнительной памяти не требуется.

Свойства

Свойство	Значение	Комментарий
Вместимость	Фиксирована	Нельзя добавить больше элементов, чем заданный размер `CAPACITY`.
Заворот	По модулю	Кольцевой эффект достигается математической операцией `(index + 1) % CAPACITY`.
Порядок	FIFO	Первым пришел - первым ушел. Сохраняет порядок добавления элементов.

Примеры реализации: Кольцевая очередь (Circular Queue)

Код на C

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

#define CAPACITY 6 // Жестко заданная вместимость кольцевой очереди

typedef struct {
    int data[CAPACITY]; // Статический массив фиксированного размера
    int head;           // Индекс головы (откуда извлекаем элементы)
    int tail;           // Индекс хвоста (куда вставляем элементы)
    int count;          // Текущее количество элементов
} CircularQueue;

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

// Проверка на переполнение
int isFull(CircularQueue* q) {
    return q->count == CAPACITY;
}

// Проверка на пустоту
int isEmpty(CircularQueue* q) {
    return q->count == 0;
}

// Добавление элемента в очередь (enqueue)
void enqueue(CircularQueue* q, int val) {
    if (isFull(q)) {
        printf("Queue is full!\n"); // Нельзя превысить CAPACITY
        return;
    }

    // Записываем значение в ячейку, на которую указывает хвост
    q->data[q->tail] = val;

    // Сдвигаем хвост с заворотом по модулю вместимости
    q->tail = (q->tail + 1) % CAPACITY;

    q->count++; // Увеличиваем счетчик элементов
}

// Извлечение элемента из очереди (dequeue)
int dequeue(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n"); // Нечего извлекать
        return -1;
    }

    // Читаем значение из ячейки, на которую указывает голова
    int val = q->data[q->head];

    // Сдвигаем голову с заворотом по модулю вместимости
    q->head = (q->head + 1) % CAPACITY;

    q->count--; // Уменьшаем счетчик элементов
    return val;
}

Код на Python

class CircularQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity # Максимальное число элементов
        self.data = [None] * capacity # Массив фиксированного размера
        self.head = 0  # Откуда читаем элементы
        self.tail = 0  # Куда пишем новые элементы
        self.count = 0 # Текущее число элементов в очереди

    def is_full(self) -> bool:
        # Очередь переполнена, если число элементов равно вместимости
        return self.count == self.capacity

    def is_empty(self) -> bool:
        # Очередь пуста, если элементов нет
        return self.count == 0

    def enqueue(self, val: int) -> bool:
        if self.is_full():
            return False # Отказ: нет свободного места

        # Кладем значение в текущую позицию хвоста
        self.data[self.tail] = val

        # Сдвигаем хвост. Операция по модулю ( % )
        # заворачивает индекс в 0 при достижении конца массива
        self.tail = (self.tail + 1) % self.capacity
        self.count += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return None # Отказ: очередь пуста

        # Запоминаем значение в голове
        val = self.data[self.head]
        self.data[self.head] = None # Очищаем ячейку (для наглядности)

        # Сдвигаем голову с заворотом через конец массива
        self.head = (self.head + 1) % self.capacity
        self.count -= 1
        return val

Код на JavaScript

class CircularQueue {
    constructor(capacity = 6) {
        this.capacity = capacity;
        // Предварительно выделяем массив фиксированного размера
        this.data = new Array(capacity).fill(null);
        this.head = 0;  // Индекс для чтения
        this.tail = 0;  // Индекс для записи
        this.count = 0; // Счетчик заполненности
    }

    isFull() {
        return this.count === this.capacity;
    }

    isEmpty() {
        return this.count === 0;
    }

    enqueue(val) {
        if (this.isFull()) return false; // Защита от переполнения

        // Записываем значение в индекс хвоста
        this.data[this.tail] = val;

        // Ключевая механика заворота: (tail + 1) mod capacity
        this.tail = (this.tail + 1) % this.capacity;

        this.count++;
        return true;
    }

    dequeue() {
        if (this.isEmpty()) return null; // Защита от чтения из пустой очереди

        // Читаем значение из индекса головы
        const val = this.data[this.head];
        this.data[this.head] = null; // Освобождаем ячейку (опционально)

        // Сдвигаем голову по кругу аналогично хвосту
        this.head = (this.head + 1) % this.capacity;

        this.count--;
        return val;
    }
}

Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про очередь на массиве и кольцевой буфер - с подробной теорией, задачами и проверочными вопросами.