C语言循环队列的表示与实现实例详解

循环队列是一种基于数组实现的队列结构，特点是队列空间的循环利用。当队列的队尾到达数组末尾时，其将循环跳回头部，队首始终处于数组的第一个位置。C语言中的循环队列的表示与实现有以下两个关键点：

1.如何判断循环队列为空？

2.如何判断循环队列已满？

在这篇文章中，将会详细讲解以上两个问题的解决方法。

循环队列的基本概念

循环队列是一种先进先出(FIFO)的数据结构，常用来存储一系列的元素。和普通队列一样，循环队列由队头和队尾两个指针定义。这两个指针都初始化为零。队头指针指向队列头部的第一个元素，队尾指针指向队列尾部的下一个位置。

一个循环队列可以用一个静态数组来表示。当元素进队时，队尾指针指向元素，同时队尾指针移动到数组的下一个空闲位置。当元素出队时，队头指针移动到下一个元素，同时队头指针指向的这个元素从队列中删除。

循环队列的定义

在C语言中，循环队列可以根据以下方式进行定义：

#define MAXSIZE 100 // 循环队列的最大容量

typedef struct {
    int data[MAXSIZE];
    int front; // 队头指针
    int rear; // 队尾指针
} CircularQueue;

在这个结构体中，data是一个整型数组，用来存放队列中的元素。front和rear分别是队头指针和队尾指针。根据上面的介绍，我们可以看到队列为空的条件就是front和rear指向同一个位置。

如何判断循环队列为空

由于循环队列的队头指针和队尾指针都是从0开始的，所以当队列为空时，其队头指针front和队尾指针rear将指向同一个位置。根据这个特点，我们可以通过如下方式来判断循环队列是否为空：

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

这里我们通过一个函数来实现判断循环队列是否为空的功能。函数的参数是一个指向CircularQueue结构体的指针，返回值为布尔型。当front和rear指向同一个位置时，函数返回true。

如何判断循环队列已满

当队列满时，其队尾指针rear将指向队列中的最后一个元素，接下来新的元素将不能再进队。由于循环队列的特殊性，当rear前进到数组的末尾时，数组将循环回到数组的开头，此时rear应该指向0。

为了判断循环队列是否已满，我们可以将rear值实际的下一个位置，也就是rear+1，与当前的front值进行比较。如果它们相等，则说明队列已满。

bool isFull(CircularQueue* q) {
    int temp = (q->rear + 1) % MAXSIZE;
    return temp == q->front;
}

这里同样使用了一个函数来实现判断循环队列是否已满的功能。函数名称为isFull，其参数为指向CircularQueue结构体的指针，返回值为布尔型。函数中使用了求模运算来实现数组的循环性，并将计算结果存储在一个临时变量temp中。当temp与front指向同一个位置时，函数返回true。

示例

下面是两个示例代码，展示了如何使用循环队列以及如何判断队列是否为空或者已满。

示例一：使用循环队列存储整型数据，并判断队列是否为空或者已满

#include <stdio.h>
#include <stdbool.h> // for bool type and true/false constant values

#define MAXSIZE 100 // 循环队列的最大容量

typedef struct {
    int data[MAXSIZE];
    int front; // 队头指针
    int rear; // 队尾指针
} CircularQueue;

// 创建一个空的循环队列
CircularQueue* createQueue() {
    CircularQueue* q = (CircularQueue*)malloc(sizeof(CircularQueue));
    q->front = q->rear = 0;
    return q;
}

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

// 判断循环队列是否已满
bool isFull(CircularQueue* q) {
    int temp = (q->rear + 1) % MAXSIZE;
    return temp == q->front;
}

int main() {
    CircularQueue* q = createQueue();

    printf("循环队列是否为空: %d\n", isEmpty(q));
    printf("循环队列是否已满: %d\n", isFull(q));

    q->data[q->rear++] = 1;
    q->data[q->rear++] = 2;
    q->data[q->rear++] = 3;

    printf("循环队列是否为空: %d\n", isEmpty(q));
    printf("循环队列是否已满: %d\n", isFull(q));

    free(q);
    return 0;
}

输出：

循环队列是否为空: 1
循环队列是否已满: 0
循环队列是否为空: 0
循环队列是否已满: 0

示例二：基于循环队列实现进程调度器

#include <stdio.h>
#include <stdbool.h> // for bool type and true/false constant values
#include <stdlib.h> // for rand() and srand()
#include <time.h> // for time()

#define MAXSIZE 100 // 循环队列的最大容量
#define MAX_PROCESS_DURATION 10 // 进程最长运行时间

// 进程结构体
typedef struct {
    int id; // 进程ID
    int duration; // 运行时间
} Process;

// 循环队列结构体
typedef struct {
    Process data[MAXSIZE];
    int front; // 队头指针
    int rear; // 队尾指针
} CircularQueue;

// 创建一个空的循环队列
CircularQueue* createQueue() {
    CircularQueue* q = (CircularQueue*)malloc(sizeof(CircularQueue));
    q->front = q->rear = 0;
    return q;
}

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

// 判断循环队列是否已满
bool isFull(CircularQueue* q) {
    int temp = (q->rear + 1) % MAXSIZE;
    return temp == q->front;
}

// 进程模拟函数，用于模拟进程的运行
void simulateProcess(int process_id, int duration) {
    printf("Process #%d running, duration: %d\n", process_id, duration);
    sleep(duration); // 模拟进程运行
}

// 随机生成一个时间
int randomDuration() {
    return rand() % MAX_PROCESS_DURATION + 1;
}

// 创建一个新的进程
Process* createProcess(int process_id) {
    Process* new_process = (Process*)malloc(sizeof(Process));
    new_process->id = process_id;
    new_process->duration = randomDuration();
    return new_process;
}

int main() {
    CircularQueue* q = createQueue();
    srand(time(NULL)); // 初始化随机数生成器

    int process_id = 1;

    while (true) {
        // 创建一个新的进程
        Process* new_process = createProcess(process_id);

        // 如果队列未满，则将进程放入队列中
        if (!isFull(q)) {
            q->data[q->rear++] = *new_process;
            printf("Process #%d created, duration: %d\n", process_id, new_process->duration);
        }
        else {
            printf("Queue is full, can't create new process!\n");
            free(new_process);
        }

        // 如果队列不为空，则从队列中取出一个进程，开始运行
        if (!isEmpty(q)) {
            Process* running_process = &q->data[q->front];
            simulateProcess(running_process->id, running_process->duration);
            printf("Process #%d finished, duration: %d\n", running_process->id, running_process->duration);
            q->front++;
        }

        process_id++;
        printf("-------------------------------\n");
        sleep(1); // 等待1秒钟
    }

    free(q);
    return 0;
}

输出（部分内容）：

Process #1 created, duration: 7
Process #2 created, duration: 10
Process #3 created, duration: 10
Process #4 created, duration: 5
Process #5 created, duration: 7
Process #6 created, duration: 10
Process #7 created, duration: 8
Process #8 created, duration: 7
Process #9 created, duration: 2
Queue is full, can't create new process!
Process #1 running, duration: 7
Process #1 finished, duration: 7
Process #2 running, duration: 10
Process #2 finished, duration: 10
Process #3 running, duration: 10