CodeUtility
Кодить проще - жить легче!
Структуры данных в C/C++

Кольцевая очередь (circular queue) в C и C++

В этом уроке вы реализуете очередь по правилу «первым пришёл, первым ушёл» на кольцевом массиве в C и с std::queue в C++.

Введение

Очередь (queue) работает по правилу «первым пришёл, первым ушёл» (FIFO). В обычном массиве после каждого извлечения пришлось бы сдвигать оставшиеся элементы. Кольцевая очередь (circular buffer) решает эту проблему: индексы возвращаются к началу, а освободившиеся места используются снова.

Главное

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

Как это работает

Делайте enqueue и dequeue и убедитесь, что элементы выходят в том же порядке, в каком пришли.

Примеры кода на C и C++

C
Запустить →
main.c
#include <stdio.h>

typedef struct {
    int data[4];
    int head;
    int size;
} Queue;

int push(Queue *queue, int value) {
    if (queue->size == 4) return 0;
    int tail = (queue->head + queue->size) % 4;
    queue->data[tail] = value;
    ++queue->size;
    return 1;
}

int pop(Queue *queue, int *value) {
    if (queue->size == 0) return 0;
    *value = queue->data[queue->head];
    queue->head = (queue->head + 1) % 4;
    --queue->size;
    return 1;
}

int main(void) {
    Queue queue = {{0}, 0, 0};
    int value;
    push(&queue, 7);
    push(&queue, 9);
    pop(&queue, &value);
    printf("%d\n", value);
}
Результат выполнения
7
C++
Запустить →
main.cpp
#include <iostream>
#include <queue>

int main() {
    std::queue<int> values;
    values.push(7);
    values.push(9);
    std::cout << values.front() << '\n';
    values.pop();
}
Результат выполнения
7

Сравнение C и C++

Очередь на C хранит позицию начала head и число элементов size. Позиция нового элемента вычисляется через остаток от деления (head + size) % 4, поэтому, дойдя до конца массива, индекс автоматически возвращается к началу. В C++ std::queue - это адаптер контейнера (container adapter), который сразу предоставляет операции front, push и pop.

C

Данные (struct) и операции разделены, а память выделяется и освобождается вручную.

C++

Классы и контейнеры защищают целостность данных и сами управляют своими ресурсами.

Упражнения для практики

Запустите обе версии, а затем измените код, чтобы увидеть разницу в безопасности, которую даёт каждый язык.

  • Добавьте тесты для пустого состояния и момента, когда достигнута максимальная ёмкость.
  • Напишите освобождение памяти и убедитесь, что утечек нет.
  • Сравните сложность с аналогичным контейнером стандартной библиотеки.

Попрактикуйтесь на задаче

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

Все задачи