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

1. Очередь на основе массива.
   Одна из самых простых реализаций — использование массива для хранения элементов. Вот пример фрагмента кода:

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} ArrayQueue;
void enqueue(ArrayQueue* queue, int element) {
    if (queue->rear == MAX_SIZE - 1) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }
    queue->data[++(queue->rear)] = element;
}
int dequeue(ArrayQueue* queue) {
    if (queue->front > queue->rear) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }
    return queue->data[(queue->front)++];
}

2. Очередь на основе связанного списка.
   Использование связанного списка в качестве базовой структуры данных позволяет динамически распределять память. Вот пример реализации:

typedef struct Node {
    int data;
    struct Node* next;
} Node;
typedef struct {
    Node* front;
    Node* rear;
} LinkedListQueue;
void enqueue(LinkedListQueue* queue, int element) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = element;
    newNode->next = NULL;
    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }
    queue->rear->next = newNode;
    queue->rear = newNode;
}
int dequeue(LinkedListQueue* queue) {
    if (queue->front == NULL) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }
    int data = queue->front->data;
    Node* temp = queue->front;
    queue->front = queue->front->next;
    if (queue->front == NULL)
        queue->rear = NULL;
    free(temp);
    return data;
}

3. Циркулярная очередь.
   Круговые очереди эффективно используют доступное пространство в очереди на основе массива. Вот пример реализации:

#define MAX_SIZE 100
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} CircularQueue;
void enqueue(CircularQueue* queue, int element) {
    if ((queue->rear + 1) % MAX_SIZE == queue->front) {
        printf("Queue is full. Cannot enqueue.\n");
        return;
    }
    queue->rear = (queue->rear + 1) % MAX_SIZE;
    queue->data[queue->rear] = element;
}
int dequeue(CircularQueue* queue) {
    if (queue->front == queue->rear) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }
    queue->front = (queue->front + 1) % MAX_SIZE;
    return queue->data[queue->front];
}

4. Динамическая очередь:
   Динамические очереди позволяют при необходимости изменять размер базового массива. Вот пример реализации:

typedef struct {
    int* data;
    int front;
    int rear;
    int capacity;
} DynamicQueue;
void enqueue(DynamicQueue* queue, int element) {
    if (queue->rear == queue->capacity - 1) {
        int* newData = (int*)malloc(2 * queue->capacity * sizeof(int));
        memcpy(newData, queue->data, queue->capacity * sizeof(int));
        free(queue->data);
        queue->data = newData;
        queue->capacity *= 2;
    }
    queue->data[++(queue->rear)] = element;
}
int dequeue(DynamicQueue* queue) {
    if (queue->front > queue->rear) {
        printf("Queue is empty. Cannot dequeue.\n");
        return -1;
    }
    return queue->data[(queue->front)++];
}

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