Циклическая очередь

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

Принцип работы

Циклическая очередь представляет собой массив фиксированной длины, доступ к элементам которого осуществляется с помощью двух указателей: head (головы) и tail (хвоста). Указатель head указывает на первый элемент очереди, готовый к извлечению, а tail — на следующую свободную позицию для добавления нового элемента. При добавлении элемента указатель tail увеличивается на единицу, а при извлечении — head. Когда любой из указателей достигает конца массива, он сбрасывается на начало (нулевой индекс), что и создаёт эффект кольца.

Основные операции

Enqueue (добавление): элемент записывается в позицию, на которую указывает tail, после чего tail сдвигается вперёд. Если очередь полна (то есть tail догоняет head), добавление невозможно.
Dequeue (извлечение): элемент считывается из позиции head, после чего head сдвигается вперёд. Если очередь пуста (то есть head равен tail), извлечение невозможно.
Peek (просмотр): возвращает элемент по указателю head без его удаления.
IsEmpty (проверка на пустоту): возвращает true, если head равен tail.
IsFull (проверка на заполненность): возвращает true, если следующая позиция после tail совпадает с head.

Управление состоянием

Для различения пустой и полной очереди существует несколько подходов. Наиболее распространённый — резервирование одной ячейки: массив объявляется размером N+1, где N — максимальное количество хранимых элементов. Очередь считается полной, если (tail + 1) % (N+1) == head. Альтернативные методы включают хранение счётчика элементов или использование флага, указывающего на состояние заполненности.

История

Концепция циклической очереди восходит к ранним разработкам в области вычислительной техники. Одним из первых практических применений стал кольцевой буфер, использованный в 1950-х годах в операционной системе для ЭВМ UNIVAC I. В 1960-х годах кольцевые буферы активно применялись в телекоммуникационных системах для синхронизации потоков данных, в частности, в протоколах передачи данных и устройствах последовательного доступа.

В советской вычислительной технике циклические очереди использовались, например, в операционной системе «Диспетчер» для ЭВМ «Минск-32» (1960-е годы) для организации очередей задач и буферизации ввода-вывода. В 1970-х годах кольцевые буферы стали стандартным элементом реализации каналов прямого доступа к памяти (DMA) в микропроцессорах.

Реализация

На языке C

Пример реализации циклической очереди фиксированного размера на языке C:

```c

define QUEUE_SIZE 10

typedef struct { int data[QUEUE_SIZE]; int head; int tail; } CircularQueue;

void initQueue(CircularQueue *q) { q->head = 0; q->tail = 0; }

int isFull(CircularQueue *q) { return (q->tail + 1) % QUEUE_SIZE == q->head; }

int isEmpty(CircularQueue *q) { return q->head == q->tail; }

int enqueue(CircularQueue *q, int value) { if (isFull(q)) return 0; q->data[q->tail] = value; q->tail = (q->tail + 1) % QUEUE_SIZE; return 1; }

int dequeue(CircularQueue q, int value) { if (isEmpty(q)) return 0; *value = q->data[q->head]; q->head = (q->head + 1) % QUEUE_SIZE; return 1; } ```

На языке Python

Пример на Python с использованием списка:

```python class CircularQueue: def __init__(self, size): self.size = size + 1 self.queue = [None] * self.size self.head = 0 self.tail = 0

def is_full(self): return (self.tail + 1) % self.size == self.head

def is_empty(self): return self.head == self.tail

def enqueue(self, item): if self.is_full(): raise OverflowError("Queue is full") self.queue[self.tail] = item self.tail = (self.tail + 1) % self.size

def dequeue(self): if self.is_empty(): raise IndexError("Queue is empty") item = self.queue[self.head] self.head = (self.head + 1) % self.size return item ```

Преимущества и недостатки

Преимущества

Эффективность использования памяти: освободившиеся ячейки сразу становятся доступны для записи, что исключает необходимость в сдвиге данных.
Постоянное время выполнения операций: как добавление, так и извлечение элемента выполняются за O(1) в худшем случае.
Простота реализации: не требуется динамического выделения памяти или сложных структур, таких как связные списки.
Предсказуемость: фиксированный размер гарантирует отсутствие фрагментации памяти.

Недостатки

Ограниченный размер: максимальное количество элементов задаётся при создании очереди и не может быть изменено динамически.
Потеря данных при переполнении: при попытке добавления в полную очередь элемент либо отвергается, либо перезаписывает самый старый (в некоторых реализациях).
Сложность масштабирования: для увеличения размера требуется создание новой очереди и копирование данных.

Применение

Циклические очереди широко используются в системном программировании, встраиваемых системах, сетевых технологиях и мультимедиа.

Операционные системы

Буферизация ввода-вывода: кольцевые буферы применяются в драйверах устройств для временного хранения данных, передаваемых между устройством и оперативной памятью. Например, в ядре Linux кольцевые буферы используются для реализации каналов (pipes) и очередей задач.
Планировщики задач: в операционных системах реального времени (RTOS) циклические очереди служат для организации очередей готовых к выполнению процессов.

Сетевые технологии

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

Встраиваемые системы

Обработка прерываний: циклические очереди используются для хранения событий, поступающих от аппаратных прерываний, до их обработки основным циклом программы.
Интерфейсы связи: в протоколах UART, SPI и I²C кольцевые буферы реализуют FIFO-буферизацию передаваемых данных.

Мультимедиа

Аудио-движки: в звуковых драйверах (например, ALSA в Linux) кольцевые буферы связывают приложение с аудиоустройством, обеспечивая непрерывный поток звуковых сэмплов.
Видео-захват: в программах записи видео кольцевые буферы позволяют временно хранить кадры до их кодирования.

Разновидности

Кольцевой буфер с перезаписью

В такой реализации при переполнении очереди новый элемент записывается поверх самого старого. Указатель head сдвигается на одну позицию вперёд, что позволяет хранить только последние N элементов. Этот вариант часто используется в системах логирования и мониторинга.

Многопоточная циклическая очередь

Для использования в многопоточных средах применяются блокировки (мьютексы, семафоры) или lock-free алгоритмы на основе атомарных операций. Например, в стандартной библиотеке C++ (std::queue) циклическая очередь не является потокобезопасной по умолчанию, но может быть адаптирована с помощью std::mutex.