C语言实现循环队列

C语言实现循环队列的完整攻略

前言

循环队列是一种常用的数据结构，用于解决队列数据访问时线性存储空间限制的问题。本文将讲解如何使用C语言实现循环队列。

队列的定义

队列是一种特殊的线性表，具有先进先出（FIFO）的特点，即最先进入队列的元素最先被取出。

循环队列的特殊之处在于，队列空间是使用连续的线性存储空间而形成的一个环。

循环队列的实现

代码实现

在C语言中，循环队列的实现可通过以下代码实现：

// 声明循环队列结构体
typedef struct {
    int* data;  // 指向队列数据域的指针
    int front;  // 队头指针
    int rear;   // 队尾指针
    int size;   // 队列大小
} CircularQueue;

// 初始化循环队列
CircularQueue* InitCircularQueue(int size) {
    CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));
    queue->data = (int*)malloc(sizeof(int) * size);
    queue->front = queue->rear = 0;
    queue->size = size;
    return queue;
}

// 判断循环队列是否为空
bool IsCircularQueueEmpty(CircularQueue* queue) {
    return queue->front == queue->rear;
}

// 判断循环队列是否已满
bool IsCircularQueueFull(CircularQueue* queue) {
    return (queue->rear + 1) % queue->size == queue->front;
}

// 往循环队列中添加元素
int AddCircularQueue(CircularQueue* queue, int value) {
    if (IsCircularQueueFull(queue)) {
        return -1;  // 队列已满，无法添加元素
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % queue->size;
    return 0;
}

// 从循环队列中取出元素
int RemoveCircularQueue(CircularQueue* queue, int* value) {
    if (IsCircularQueueEmpty(queue)) {
        return -1;  // 队列为空，无法取出元素
    }
    *value = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->size;
    return 0;
}

// 销毁循环队列，释放内存空间
void DestroyCircularQueue(CircularQueue* queue) {
    free(queue->data);
    free(queue);
}

代码说明

上述代码中，定义了一个CircularQueue类型的结构体，其中包含了指向队列数据域的指针data，队头指针front，队尾指针rear，队列大小size四个成员。

接着，使用InitCircularQueue函数初始化循环队列，并在其中调用malloc函数分配数据空间，最后返回循环队列的指针。

在进行队列操作时，通过AddCircularQueue函数往队列中添加元素，通过RemoveCircularQueue函数将队列中的元素取出。

需要说明的是，为了避免“队尾指针指向数据空间的尾部而未满，队头指针指向数据空间的头部而为空”的歧义情况，循环队列中将队列的尾部指针(rear)指向下一个数据存放的位置。因此，判断队列是否为空的条件为队头指针(front)与队尾指针(rear)相等，而判断队列是否为满的条件为队列的下一位为队头指针(front)。

示例说明

示例1：使用循环队列解决Josephus问题

Josephus问题是一个著名的数学游戏，有N个人围成一圈，编号从1到N，从某个编号开始报数，数到M的人出列，之后从下一个人开始重新报数。求出最后留下的人的编号。

使用循环队列可以轻松地解决Josephus问题。下面是C语言实现代码及注释：

#include <stdio.h>
#include <stdlib.h>

// 声明循环队列结构体
#include "circlequeue.h"

int main() {
    int N = 10;   // 总人数
    int M = 3;    // 报数的周期
    int i, j;
    int e, a[N];  // 声明临时变量和数组
    CircularQueue* q;  // 声明循环队列指针
    q = InitCircularQueue(N);  // 初始化循环队列
    for (i = 0; i < N; i++) {
        AddCircularQueue(q, i + 1);  // 将人员编号依次加入队列
    }
    for (i = 0; i < N; i++) {
        RemoveCircularQueue(q, &e);  // 模拟报数，出队列
        a[i] = e;  // 将出队列的人员编号存放到数组中
        for (j = 1; j < M; j++) {
            RemoveCircularQueue(q, &e);  // 模拟报数，不出队列
            AddCircularQueue(q, e);      // 将不出队列的人员重新加入队列
        }
    }
    printf("出列顺序：");
    for (i = 0; i < N; i++) {
        printf("%d ", a[i]);  // 输出出列顺序
    }
    printf("\n最后留下：%d\n", e);  // 输出最后留下的人员编号
    DestroyCircularQueue(q);  // 删除队列，释放内存空间
    return 0;
}

示例2：使用循环队列模拟打印任务调度

使用循环队列可以方便地模拟打印任务的调度。下面是C语言实现代码及注释：

#include <stdio.h>
#include <stdlib.h>

// 声明循环队列结构体
#include "circlequeue.h"

int main() {
    int max_task_num = 6;   // 最大任务数
    int task_left = 0;      // 等待执行的任务数
    int executing_task_id;  // 当前正在执行的任务ID
    int i;
    CircularQueue* queue;   // 声明循环队列指针
    queue = InitCircularQueue(max_task_num);  // 初始化循环队列
    while (1) {
        printf("\n********************\n");      
        printf("等待任务：%d，", task_left);  // 打印等待任务数
        if (!IsCircularQueueEmpty(queue)) {
            printf("队列头部任务：[%d]\n", queue->data[queue->front]);  // 打印队列中最前面的任务
        } else {
            printf("无任务\n");  // 如果队列为空则输出“无任务”
        }
        printf("********************\n\n");      

        // 获取用户输入
        printf("请输入命令（a-添加任务，e-执行任务）：");
        char cmd = getchar();
        while (getchar() != '\n')
            ;
        if (cmd == 'a') {  // 添加任务
            if (!IsCircularQueueFull(queue)) {
                AddCircularQueue(queue, max_task_num - task_left);  // 添加任务ID
                task_left++;  // 可执行任务数加1
                printf("添加成功，当前等待任务：%d\n", task_left);
            } else {
                printf("任务队列已满，无法添加任务\n");
            }
        } else if (cmd == 'e') {  // 执行任务
            if (!IsCircularQueueEmpty(queue)) {
                RemoveCircularQueue(queue, &executing_task_id);  // 取出队列中最前面的任务
                task_left--;  // 可执行任务数减1
                printf("任务[%d]开始执行，当前等待任务：%d\n", executing_task_id, task_left);
            } else {
                printf("任务队列为空，无法执行任务\n");
            }
        } else {
            printf("无效命令\n");
        }
    }
    DestroyCircularQueue(queue);  // 删除队列，释放内存空间
    return 0;
}

总结

本文介绍了C语言如何实现循环队列，包括定义循环队列结构体、初始化循环队列、判断队列是否为空、判断队列是否已满、往队列中添加元素、从队列中取出元素、销毁循环队列等操作。

同时，本文还提供了两个使用循环队列的示例：使用循环队列解决Josephus问题和使用循环队列模拟打印任务调度。这些示例可以帮助读者更好地理解和应用循环队列。