Структура данных - очередь

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

Понятие и принцип очереди

Очередь — иллюстрация принципа FIFO
Голова
голова
→
20
30
Хвост
хвост
← dequeueenqueue →

enqueue: вставка в хвост | dequeue: удаление из головы | Сложность O(1)

Проверка FIFO: enqueue 10→20→30, dequeue 10→20→30 (первым пришёл — первым вышел)

Очередь позволяет вставку только с одного конца (в хвост) и удаление с другого конца (из головы).

Это прямо противоположно принципу LIFO стека.

Реализация очереди с помощью массива

Пример

#include <stdio.h>
#include <stdbool.h>

#define MAX 100

struct Queue {
    int items[MAX];
    int front;   /* указатель front: указывает на первый элемент */
    int rear;    /* указатель rear: указывает на следующую позицию вставки */
};

void initQueue(struct Queue* q) {
    q->голова = 0;
    q->хвост = 0;
}

bool isEmpty(struct Queue* q) {
    return q->front == q->rear;
}

bool isFull(struct Queue* q) {
    return q->rear == MAX;
}

/* enqueue: добавить элемент в rear */
void enqueue(struct Queue* q, int value) {
    if (isFull(q)) {
        printf("Очередь заполнена!"\n");
        return;
    }
    q->items[q->rear++] = value;  /* записываем в rear, затем сдвигаем rear назад */
    printf("enqueue: %d\n", value);
}

/* dequeue: удалить элемент из начала */
int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Очередь пуста!"\n");
        return -1;
    }
    return q->items[q->front++];  /* вернуть элемент из начала, затем сдвинуть front назад */
}

int main() {
    struct Queue q;
    initQueue(&q);

    enqueue(&q, 10);  /* enqueue: 10 */
    enqueue(&q, 20);  /* enqueue: 20 */
    enqueue(&q, 30);  /* enqueue: 30 */

    printf("dequeue: %d\n", dequeue(&q));  /* вывод: dequeue: 10 (FIFO) */
    printf("dequeue: %d\n", dequeue(&q));  /* вывод: dequeue: 20 */
    printf("dequeue: %d\n", dequeue(&q));  /* вывод: dequeue: 30 */
    return 0;
}

Очередь, реализованная с помощью обычного массива, имеет проблему "ложного переполнения": по мере того как enqueue и dequeue продолжаются, front и rear продолжают смещаться к концу массива, и даже если в начале массива есть много пустого места, его нельзя использовать повторно. Решение — использоватькольцевую очередь。

кольцевую очередь

Кольцевая очередь — операция по модулю для зацикливания указателя

Ключевые формулы для кольцевой очереди

enqueue: items[rear] = value; rear = (rear + 1) % MAX;

dequeue: value = items[front]; front = (front + 1) % MAX;

Проверка на пустоту: front == rear | Проверка на полноту: (rear + 1) % MAX == front

Пример работы (ёмкость=5, максимум 4 элемента): enqueue 10→20→30→40, dequeue 10→20, enqueue 50→60 → 60 сохраняется по индексу 0 (циклический переход), идеально повторно используя освобождённое пространство.

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

Пример

#include <stdio.h>
#include <stdbool.h>

#define MAX 5 /* намеренно задана маленькая ёмкость, чтобы эффект зацикливания было легче наблюдать */

struct CircularQueue {
    int items[MAX];
    int front;  /* индекс front */
    int rear;   /* индекс rear (следующая позиция вставки) */
};

void initQueue(struct CircularQueue* q) {
    q->голова = 0;
    q->хвост = 0;
}

/* проверка на пустоту: front и rear совпадают */
bool isEmpty(struct CircularQueue* q) {
    return q->front == q->rear;
}

/* проверка на полноту: (rear + 1) % MAX == front Примечание: в кольцевой очереди намеренно оставляют одну позицию пустой, чтобы отличать пустое состояние от полного */
/* enqueue: записать в rear, затем переместить rear по кругу вперёд */
bool isFull(struct CircularQueue* q) {
    return (q->rear + 1) % MAX == q->голова;
}

"Кольцевая очередь заполнена!
void enqueue(struct CircularQueue* q, int value) {
    if (isFull(q)) {
        printf(/* остаток по модулю для циклического перехода */\n");
        return;
    }
    q->items[q->rear] = value;
    q->rear = (q->rear + 1) % MAX;  "enqueue: %d (rear=%d)
    printf(/* dequeue: вернуть элемент из начала, затем переместить front вперёд циклически */\n", value, q->хвост);
}

/* Dequeue: вернуть элемент в начале, затем front перемещается вперёд циклически */
int dequeue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Кольцевая очередь пуста!\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front = (q->front + 1) % MAX;  /* Операция по модулю обеспечивает циклический переход */
    return value;
}

int main() {
    struct CircularQueue q;
    initQueue(&q);

    enqueue(&q, 10);  /* Постановка в очередь: 10 (rear=1) */
    enqueue(&q, 20);  /* Постановка в очередь: 20 (rear=2) */
    enqueue(&q, 30);  /* Постановка в очередь: 30 (rear=3) */
    enqueue(&q, 40);  /* Постановка в очередь: 40 (rear=4) — вместимость 5, максимум 4 элемента */

    printf("Извлечение: %d\n", dequeue(&q));  /* Извлечение: 10 (front=1) */
    printf("Извлечение: %d\n", dequeue(&q));  /* Извлечение: 20 (front=2) */

    enqueue(&q, 50);  /* Постановка в очередь: 50 (rear=0 — циклически переходит в начало!) */
    enqueue(&q, 60);  /* Постановка в очередь: 60 (rear=1) */

    printf("Оставшиеся элементы: ");
    while (!isEmpty(&q)) {
        printf("%d ", dequeue(&q));
    }
    printf("\n");  /* Вывод: Оставшиеся элементы: 30 40 50 60 */
    return 0;
}

Сценарии применения очереди

Сценарии примененияОписание
Поиск в ширину (BFS)Обходить узлы графа уровень за уровнем; нужна очередь для хранения узлов, "подлежащих посещению"
Планирование задач операционной системыЦП выделяет кванты времени в порядке поступления задач
Очередь задач печатиНесколько компьютеров совместно используют один принтер; запросы на печать ставятся в очередь и обрабатываются в порядке отправки
Очередь сообщенийВ распределённых системах сообщения, создаваемые производителями, передаются потребителям через очередь
Другие расширения