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

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

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

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

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

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

循环队列的基本概念

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

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

循环队列的定义

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

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

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

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

如何判断循环队列为空

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

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

这里我们通过一个函数来实现判断循环队列是否为空的功能。函数的参数是一个指向CircularQueue结构体的指针,返回值为布尔型。当frontrear指向同一个位置时,函数返回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中。当tempfront指向同一个位置时,函数返回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

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:C语言循环队列的表示与实现实例详解 - Python技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • 辐射4人员属性设定详细分析

    辐射4人员属性设定详细分析 在辐射4中,人员属性设定对游戏的角色扮演和流程起着很大的作用。本文将详细分析人员属性设定的每个部分,并提供一些有用的技巧和建议。 S.P.E.C.I.A.L S.P.E.C.I.A.L.代表了Strength(力量)、Perception(感知)、Endurance(耐力)、Charisma(魅力)、Intelligence(智力…

    C 2023年5月22日
    00
  • 详解JavaScript的BUG和错误

    标题:详解JavaScript的BUG和错误 首先,让我们对JavaScript的错误和bug进行概述。 JavaScript中的错误分为两种类型: 语法错误和运行时错误。语法错误是在代码编写阶段就能检测到的,它们在JavaScript的解释执行过程中被捕获。例如,如果您错写了一个变量名或忘记了一个括号,则会产生语法错误。运行时错误在代码运行期间发生,它们通…

    C 2023年5月22日
    00
  • C语言自制测色弱找方块游戏的示例代码

    下面我来详细讲解“C语言自制测色弱找方块游戏的示例代码”的完整攻略。 程序简介 该程序是一款基于C语言编写的测色弱能力的小游戏,玩家需要在屏幕上找到某个特定颜色方块,并点击该方块。同时,该程序还能够较为准确地检测用户的色盲情况。如果用户识别出的颜色与程序给出的颜色不符,则会提示用户是否为色盲人士。 程序设计 程序主要由两个部分组成:图像处理和游戏逻辑处理。图…

    C 2023年5月24日
    00
  • 解决Vue-Router升级导致的Uncaught (in promise)问题

    当将Vue-Router从版本2升级到版本3时,可能会遇到一个非常常见的问题,就是Uncaught (in promise)错误。这是由于Vue-Router版本3采用了Promise API,而在旧版中未正确使用Promise时造成的。 要解决这个问题,有以下两个简单的步骤: 步骤一:升级Vue-Router到最新版本 首先要确保已将Vue-Router版…

    C 2023年5月23日
    00
  • C语言中如何控制程序流程?

    控制程序流程是C语言中非常重要的一个方面,主要通过条件语句、循环语句以及函数调用来实现。下面我将详细讲解。 条件语句 条件语句用于根据条件来执行不同的代码块。C语言中,最常用的条件语句为if…else语句和switch语句。 if…else语句 if…else语句用于在满足特定条件时执行代码块。如果条件为真,则执行if代码块,否则执行else代码…

    C 2023年4月27日
    00
  • C++编译期循环获取变量类型详情

    下面我将为您详细讲解 C++ 编译期循环获取变量类型的完整攻略。 什么是编译期循环获取变量类型? 在 C++ 中,有时候我们需要获取一个集合中特定元素的类型,如果使用运行时的方法获取,需要使用运行时类型信息(RTTI)机制,速度较慢。而编译期循环获取变量类型则是一种优雅的方式,它可以在编译的时候直接获取到想要的类型信息,更加高效。 如何实现编译期循环获取变量…

    C 2023年5月23日
    00
  • Java实现API sign签名校验的方法详解

    Java实现API sign签名校验的方法详解 简介 在互联网应用的开发过程中,API被广泛应用。而在API的开发过程中,为了确保API的安全性,一般都会使用签名验证的方式进行校验。而在Java中,实现API sign签名校验的方法也是比较简单的。 签名算法的原理 在进行签名校验之前,我们先来了解一下签名算法的原理。 签名算法是指通过一定的算法和密钥来对一个…

    C 2023年5月23日
    00
  • NBA2KOL毕比投篮包怎么样 C级球员投篮包介绍

    NBA2KOL毕比投篮包攻略 毕比投篮包是什么? 毕比投篮包是NBA2KOL中的一种投篮练习工具,可以用来提高球员的投篮技能。不同的投篮包适用于不同类型的球员,毕比投篮包适用于C级球员。 如何使用毕比投篮包? 进入游戏,在主菜单中选择“训练”选项。 选择毕比投篮包练习,并进入投篮练习场地。 在练习场地中,你需要使用队伍中的C级球员进行投篮练习。使用左侧列表中…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部