Очередь (Queue) довольно простая структура данных. У неё две ключевые операции:

• enqueue(): добавить в конец

• dequeue(): удалить из начала

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

Очередь часто реализуется на массиве (ArrayDeque в Java и collections.deque в Python), используя два указателя: front и rear.

Проблема: почему обычная очередь на массиве неэффективна?

• После нескольких операций enqueue и dequeue, свободные ячейки в начале массива не используются.

• В итоге массив может казаться «переполненным», хотя там ещё есть пустые позиции.

Пример поведения обычной очереди:

Обычная очередь (Regular queue):

1) Создаем пустую очередь с размером = 5
Состояние очереди: [_, _, _, _, _]  (front=0, rear=0)

2) Вызываем операции: enqueue(A), enqueue(B), enqueue(C), enqueue(D), enqueue(E)
Состояние после: [A, B, C, D, E]  (front=0, rear=4)

3) Вызываем операцию: dequeue() → удаляет A
Состояние после: [_, B, C, D, E]  (front=1, rear=4)

4) Вызываем операцию: dequeue() → удаляет B
Состояние после: [_, _, C, D, E]  (front=2, rear=4)

// Очередь считается "переполненной", 
// хотя в начале есть свободные ячейки

Хотя есть 2 пустые ячейки слева, новые элементы уже нельзя добавить. Это называется ложное переполнение.

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

Что такое Circular Queue?

Это оптимизированная версия обычной очереди на массиве фиксированной длины. Она решает проблему «ложного переполнения», когда свободные ячейки в начале массива остаются неиспользованными.

Главная идея: массив рассматривается как замкнутый круг. Если указатель достигает конца массива, он не останавливается, а возвращается к началу.

Таким образом, в кольцевой очереди все ячейки массива могут быть эффективно использованы, и не нужно выполнять сдвиги элементов.

Аналогия из жизни: колесо обозрения

Представьте карусель обозрения с кабинками:

• Посетители садятся в свободные кабинки по порядку (enqueue).

• Когда круг завершается, первые кабинки подъезжают к выходу, и люди выходят (dequeue).

• Кабинки снова становятся свободными и сразу же доступны для новых посетителей.

Так работает Circular Queue: массив используется как «карусель», где начало и конец соединены, и каждое место рано или поздно переиспользуется.

Визуализация поведения Кольцевой очереди:

Кольцевая очередь (Circular queue):

1) Создаем пустую очередь с размером 5
Состояние очереди: [_, _, _, _, _]  (front=0, rear=0)

2) Вызываем операции: enqueue(A), enqueue(B), enqueue(C), enqueue(D), enqueue(E)
Состояние после: [A, B, C, D, E]  (front=0, rear=4)

3) Вызываем операцию: dequeue() → удаляет A
Состояние после: [_, B, C, D, E]  (front=1, rear=4)

4) Вызываем операцию: dequeue() → удаляет B
Состояние после: [_, _, C, D, E]  (front=2, rear=4)

5) Вызываем операцию: enqueue(F) // оборачивается в начало
Состояние после: [F, _, C, D, E]  (front=2, rear=0)

5) Вызываем операцию: enqueue(H)
Состояние после: [F, H, C, D, E]  (front=2, rear=1)

// Теперь очередь по-настоящему переполнена
// и использует всё пространство.

Зачем учить Circular Queue?

Понимание и реализация Circular Queue важны, потому что наивная очередь на массиве сталкивается с проблемой «ложного переполнения», освободившиеся места в начале массива не используются. Это ведёт к неэффективности и ошибкам.

Освоение техники Circular Queue помогает:

• научиться работать с индексами по модулю, что часто встречается в алгоритмах;

• увидеть практическое применение в системах с ограниченными ресурсами: сетевые буферы, обработка потоков, очереди задач в реальном времени.

📌 В стандартных библиотеках Java (ArrayDeque) и Python (collections.deque) очередь реализована на основе кольцевого буфера (Circular Queue). Поэтому важно освоить эту технику. Она объясняет, как под капотом работают готовые API, и помогает уверенно применять их в реальных задачах.

С концепцией Circular Queue мы ознакомились в предыдущем разделе.

Здесь будут рассмотрены детали реализации: как устроены индексы front и rear, как выполняются операции вставки и удаления, и какие ошибки чаще всего возникают.

В этой статье разбираются четыре ключевые ситуации:

1. Обычная вставка (enqueue)

2. Вставка с оборачиванием (enqueue wrap)

3. Обычное удаление (dequeue)

4. Удаление с оборачиванием (dequeue wrap)

1. Enqueue: вставка элемента

Обычная вставка (regular enqueue)

Если хвост (rear) ещё не дошёл до конца массива, вставка выполняется в следующую позицию.

До:
[ 10 | 20 | 30 | _ | _ ]  
front = 0, rear = 2

enqueue(40)
После:
[ 10 | 20 | 30 | 40 | _ ]  
front = 0, rear = 3

Вставка с Оборачиванием (wrap-around enqueue)

Если rear находится в конце массива, но в начале есть свободные ячейки (после удалений), хвост «оборачивается» и продолжает вставку с начала.

До:
[ _ | _ | 30 | 40 | 50 ]  
front = 2, rear = 4

enqueue(60)
После:
[ 60 | _ | 30 | 40 | 50 ]  
front = 2, rear = 0

Псевдокод

void enqueue(x):
    if ((rear + 1) % capacity == front):    // очередь полна
        ошибка "Queue is full"
    else if (front == -1):                  // вставка первого элемента
        front = 0
        rear = 0
    else:
        rear = (rear + 1) % capacity        // движение по кругу
    queue[rear] = x                         // вставка нового элемента

Dequeue: удаление элемента

Обычное удаление (regular dequeue)

Если front меньше rear, элемент удаляется напрямую, а голова сдвигается вправо.

До:
[ 10 | 20 | 30 | 40 | _ ]  
front = 0, rear = 3

dequeue()
После:
[ _ | 20 | 30 | 40 | _ ]  
front = 1, rear = 3

Удаление с Оборачиванием (wrap-around dequeue)

Если front достиг конца массива, после удаления он должен «обернуться» и начать снова с начала массива.

До:
[ 60 | _ | 30 | 40 | 50 ]  
front = 4, rear = 1

dequeue()
После:
[ 60 | _ | 30 | 40 | _ ]  
front = 0, rear = 1

Псевдокод

int dequeue():
    if (front == -1):                       // очередь пуста
        ошибка "Queue is empty"
    value = queue[front]                    // сохраняем удаляемый элемент
    if (front == rear):                     // остался один элемент
        front = -1
        rear = -1                           // очередь становится пустой
    else:
        front = (front + 1) % capacity      // движение по кругу
    return value

LeetCode Задачи:

622. Design Circular Queue

Совет

В технике Circular Queue ключ к правильной работе является контроль индексов и понимание циклического движения по массиву:

1. При вставке (enqueue): индекс rear всегда смещается по модулю длины массива: (rear + 1) % capacity. Это предотвращает выход за границы и обеспечивает «оборачивание».

2. При удалении (dequeue): аналогично обновляется front: (front + 1) % capacity. После удаления последнего элемента оба индекса нужно сбросить в -1.

3. Условие переполнения: корректное сравнение: (rear + 1) % capacity == front. Простое front == rearприводит к ложному срабатыванию.

4. FIFO сохраняется только при разделении ролей: front отвечает за удаление, rear за вставку. Их путаница ломает очередь.

Эта реализация основана на массиве и показывает, как эффективно переиспользовать ограниченную память.
Также Circular Queue можно реализовать на связанном списке(LinkedList), но у такого подхода есть недостаток: он требует дополнительной памяти для ссылок и теряет преимущество компактности массива.

Результат

Понимание и реализация всех четырёх случаев Circular Queue Technique помогает:

• полностью освоить принцип повторного использования памяти;

• уверенно работать с индексами и арифметикой по модулю;

• понимать внутреннюю реализацию очередей в ArrayDeque (Java) и collections.deque (Python);

• легко переходить к более сложным структурам: Deque, Ring Buffer, Blocking Queue.