程序员经验分享-hwhale

入门数据结构，c语言实现循环队列实现（详细篇）。

2023-11-07

目录

一、前言

二、循环队列的概念

三、实现循环队列

1、头文件与特殊函数介绍

2、循环队列的结构体

3、队列的初始化

4、判断队列是否为空

5、队列的进队操作

6、队列的出队操作

7、返回队头

8、返回队列长度

9、放回队列容量大小

10、销毁队列

四、完成队列（队列完整代码）

五、结束语

一、前言

在学习数据结构的过程中，学习到循环队列这，难度开始上升，之后的树、图等结构，会更加抽象并且难以实现，对逻辑更加严格，如果你正在学习数据结构，那么请你认真本篇文章，一定会有收获！

本章的主题是循环队列，所以在这里就不复习队列的基本概念。

二、循环队列的概念

循环队列一般都是基于数组结构实现的，利用数组结构我们可以很轻松的模拟出如图所视的环形循环结构：

当然链表结构也是可以实现的（可以使用循环链表进行实现）。

因为我们主要使用数组结构进行实现，所以在这篇文章中，我们主要讨论基于数组结构的实现方式。

三、实现循环队列

注意：为了好理解，之后出现的队列是循环队列的意思（可不是想偷个懒啊，哈哈）。

1、头文件与特殊函数介绍

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

本次队列需要的头文件。

1.我们需要使用一个断言函数 ：assert（判断内容），作用如果判断内容为假，则显示判断内容，同时终止程序！

例：

#include <stdio.h>
#include <assert.h>
#include <math.h>
 
int main(void)
{
    double x = -1.0;
    assert(x >= 0.0);
    printf("sqrt(x) = %f\n", sqrt(x));   
 
    return 0;
}

结果：

判断内容为假，程序终止!

2.我们使用exit函数进行终止程序。

  • exit(x)（x不为0）都表示异常退出
  • exit(0)表示正常退出

这里为什么不都用assert进行终止程序？主要是考虑到assert使用方式，assert主要是终止已知问题。

例：

当用户调用函数，实参不符合函数要求时。

但使用malloc返回一个空指针却不行，因为malloc返回空指针有多种问题造成，原因不清，所以不能使用assert来终止程序。

2、循环队列的结构体

typedef void queue;

typedef struct Tag_Queue {
	int* m; //指向动态创建数组的指针
	int front; //队列的头下标
	int rear; //队列的尾下标
	int capacity; //队列的容量大小
}Tag_Queue;

这里我们使用 queue是对我们循环队列结构体进行封装。

这里我为一些对c语言封装不太了解的读客，解释一下queue的封装原理。

void为空类型，void*他可以指向任意的地址。

当我们要调出用void*指向地址里的数据时，只需创建该地址相同类型的指针并将void*进行强制转换为相同类型，即可。

如：

#include<stdio.h>
int main(void)
{
    int x = 123;
    int* p = &x;
    void* test = p;
    
    int* p2 = (int*)test; //进行强制转换赋值

    printf("%d\n", *p2); //访问p指向地址的数据，即p指向地址的数据

    return 0;
}

结果：

指向动态创建数组的指针（m）使用指针是为了动态创建数组，使队列相对灵活，本队列存储int类型的数据，想要存储其他类型的数据可以改变m的类型。

队列的头下标（front）与尾下标（tail）的作用，可以进行队空、队满的判断，并且提供进队、出队的操作。

队列的容量（capacity）大小的作用，队列大小（size）计算必要条件之一，辅助本队列实现动态化内存管理。

3、队列的初始化

在c语言中初始化一个结构体有很多中方式，比如直接实例化（不建议使用），或者把指针传递到函数，进行内部数据的初始化。

这里我采取比较实用的方式：创建初始化函数，返回队列结构体指针（注意：这里之后会用queue进行封装）。

queue* Queue_init(int number = 0) { //可以默认初始化
	assert(number >= 0); //队列大小至少为0

	Tag_Queue* ret = (Tag_Queue*)malloc(sizeof(Tag_Queue)); //创建队列
	if (ret == NULL) { //检查队列是否创建成功
		printf("ret == NULL\n");
		exit(1);
	}
	ret->m = (int*)calloc((size_t)number + (size_t)1, sizeof(int)); //创建数组
	if (ret == NULL) { //检查数组是否创建成功
		printf("ret->m == NULL\n");
		exit(1);
	}

	ret->front = 0;
	ret->rear = 0;
	ret->capacity = number;

	return ret;
}
​

1.在创建数组时，我用（size_t）number+(size_t)1，这里是因为calloc的参数为size_t，我用vs编译器，那么size_t就为8个字节，而number为int类型与1（也为int类型）进行计算有可能导致数据溢出（这不是本单元重点，不加size_t也是可以的），我们需要注意的是这里我加了个1，这个1是我们循环队列的关键，我们看图理解。

这里我们是用rear == front来判断是否为空，用（rear+1）%capacity == front是否队满,每当进队一个元素，该元素会在rear下标当前位置进行存储，然后rear下标往前走。

但如果没有这多出来的存储单元呢？

 如图所示，当没有这多出来的存储单元的时候，安装我上面所述逻辑，队满操作就会失败！！

如果你的好好思考会发现，换别的逻辑方式也会导致判断失败，当然了，不一定是队满，也可能是队空！

本编只给出多创建一个存储单元的例子来解决这个问题！想解决这个问题也可以 使用比如计数方式，这里也就不做过多的赘述。

4、判断队列是否为空

int Queue_empty(queue* q) {
	assert(q != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)q; //进行强制转换，使后续可以操作队列

	if (ret->front == ret->tail) {
		return 1;
	}
	else {
		return 0;
	}
}
​/*返回值：1 此队列为空
         0 此队列不空*/

5、队列的进队操作

​void Queue_push(queue* q, int size) {
	assert(q != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)q; //进行强制转换，使后需可以操作队列

	if ((ret->rear + 1) % ret->capacity == ret->front) {
		int* temp = (int*)realloc(ret->m, sizeof(int) * ((size_t)ret->capacity + (size_t)16));
		if (temp == NULL) {
			printf("temp == NULL\n");
			exit(1);
		}

		ret->m = temp;
		ret->capacity = ret->capacity + 16;
	}

	ret->m[ret->rear] = size; //进队
	ret->rear = (ret->rear + 1) % ret->capacity; //尾下标向前移动一位，%capacity防止下标越界

	return;
}

在队列的进队操作中，我用了动态化的进队方式，使队列的容量随着队满进行扩容，因此支持初始化函数不传入实参。

这里我先判断队列是否满，如果满进入if语句。

创建一个临时指针temp接收realloc函数对队列内数组进行扩容后返回的int类型指针（这里如果对realloc不太了解的同学可以上网查找相关文档，这里简单阐述一下：realloc就是对第一个行参所指向的堆（heap）内存进行扩容，扩容大小为第二个行参所传值，他的扩容有两种情况，这里就不做过多赘述），扩容大小为原来的容量加16，然后在判断一下扩容是否成功，成功后，将扩容后的地址赋值给原指针，在将容量加16，扩容操作就此完成。

之后的操作看代码上的注释即可。

6、队列的出队操作

void Queue_pop(queue* p) {
	assert(p != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列

	if (Queue_empty(p) == 1) { //调用Queue_empty判断队列是否为空，若为空终止程序
		exit(1);
	}

	ret->front = (ret->front + 1) % ret->capacity; //出队后，队头下标往前移动， %capacity防止下标溢出

	return;
}

7、返回队头

int Queue_top(queue* p) {
	assert(p != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列

	if (Queue_empty(ret) == 1) { //调用Queue_empty判断队列是否为空， 若为空终止程序
		printf("Queue = empty\n");
		exit(1);
	}

	return ret->m[ret->front]; //返回队头数据
}

8、返回队列长度

int Queue_size(queue* p) {
	assert(p != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列

	return (ret->tail - ret->front + ret->capacity) % ret->capacity;
}

这里返回值的计算我们需要从两方面去考虑：

1.如图：

当rear >= front 时 我们的返回值就为 rear - front。

可我们这是循环队列，所以就会发生 rear < front，因此我们就需要多考虑一种可能。

2.如图：

当rear < front 时 我们的返回值就为 rear - front + capacity。

综上两种可能得出 队列长度为 （rear - front + capacity）% capacity。

9、放回队列容量大小

int Queue_capacity(queue* p) {
	assert(p != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列

	return ret->capacity;
}

10、销毁队列

void Queue_clear(queue**p) { //利用二级指针，控制指针
	assert(p != NULL); //判断队列是否存在

	Tag_Queue* ret = (Tag_Queue*)*p; //进行强制转换，使后续可以操作队列

	free(ret->m); //将数组进行销毁
	free(ret); //将队列结构体进行销毁

	*p = NULL; //将指针指向NULL，防止成为野指针

	return;
}

四、完成队列（队列完整代码）

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

typedef void queue;

typedef struct Tag_Queue {
	int* m;
	int front;
	int tail;
	int capacity;
}Tag_Queue;

queue* Queue_init(int number = 0) {
	assert(number >= 0);

	Tag_Queue* ret = (Tag_Queue*)malloc(sizeof(Tag_Queue));
	if (ret == NULL) {
		printf("ret == NULL\n");
		exit(1);
	}
	ret->m = (int*)calloc((size_t)number + (size_t)1, sizeof(int));
	if (ret == NULL) {
		printf("ret->m == NULL\n");
		exit(1);
	}

	ret->front = 0;
	ret->tail = 0;
	ret->capacity = number;

	return ret;
}

int Queue_empty(queue* q) {
	assert(q != NULL);

	Tag_Queue* ret = (Tag_Queue*)q;

	if (ret->front == ret->tail) {
		return 1;
	}
	else {
		return 0;
	}
}

void Queue_push(queue* q, int size) {
	assert(q != NULL);

	Tag_Queue* ret = (Tag_Queue*)q;

	if ((ret->tail + 1) % ret->capacity == ret->front) {
		int* temp = (int*)realloc(ret->m, sizeof(int) * ((size_t)ret->capacity + (size_t)16));
		if (temp == NULL) {
			printf("temp == NULL\n");
			exit(1);
		}

		ret->m = temp;
		ret->capacity = ret->capacity + 16;
	}

	ret->m[ret->tail] = size;
	ret->tail = (ret->tail + 1) % ret->capacity;

	return;
}

int Queue_top(queue* p) {
	assert(p != NULL);

	Tag_Queue* ret = (Tag_Queue*)p;

	if (Queue_empty(ret) == 1) {
		printf("Queue = empty\n");
		exit(1);
	}

	return ret->m[ret->front];
}

void Queue_pop(queue* p) {
	assert(p != NULL);

	Tag_Queue* ret = (Tag_Queue*)p;

	if (Queue_empty(p) == 1) {
		exit(1);
	}

	ret->front = (ret->front + 1) % ret->capacity;

	return;
}

int Queue_size(queue* p) {
	assert(p != NULL);

	Tag_Queue* ret = (Tag_Queue*)p;

	return (ret->tail - ret->front + ret->capacity) % ret->capacity;
}

int Queue_capacity(queue* p) {
	assert(p != NULL);

	Tag_Queue* ret = (Tag_Queue*)p;

	return ret->capacity;
}
void Queue_clear(queue**p) {
	assert(p != NULL);

	Tag_Queue* ret = (Tag_Queue*)*p;

	free(ret->m);
	free(ret);

	*p = NULL;

	return;
}

五、结束语

写完后，发现写的有点长，哈哈哈！！回头看了看，发现有一些地方有点啰嗦，想把她们删掉，但再三考虑后还是没有删，如果能看到这里，真的是非常感谢，如果哪有疑问或本章哪个位置出来了错误或者有什么建议，可以在评论区进行评论，感觉支持！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

c语言

入门数据结构，c语言实现循环队列实现（详细篇）。 的相关文章

随机推荐

  • python语言开发环境搭建_Python学习之路 （一）开发环境搭建-Go语言中文社区

    目录 目录 正文 前言 python3应该是Python的趋势所在 当然目前争议也比较大 这篇随笔的主要目的是记录在centos6 7下搭建python3环境的过程 以及碰到的问题和解决过程 另外 如果本机安装了python2 尽量不要管他

  • SpringCloud-服务网关

    服务网关 GateWay 核心简介 上一代zuul 1 x官网 Gateway官网 概述 Cloud全家桶中有个很重要的组件就是网关 在1 x版本中都是采用的Zuul网关 但在2 x版本中 zuul的升级一直跳票 SpringCloud最后

  • # Vue 配置前端后端路由地址

    Vue 配置前端后端路由地址 文章目录 Vue 配置前端后端路由地址 前端路由配置 配置项目地址 配置页面路由 路径跳转 后端路由配置 配后端请求地址 前端路由配置 配置项目地址 修改 config index js的配置文件 proxyT

  • jvm监控工具之jvisualvm&jmc

    一 jvisualvm 监控 方法一 使用 jstatd 1 创建策略文件 jstatd all policy 内容如下 grant codebase file java home lib tools jar permission java

  • 许奔创新社-第7问：构建创意的液态网络需要哪些条件？

    在 创意诞生的关键要素 中 我们曾提到一个非常重要的问题 对于体量差异不大的液态网络 为什么有的能产出大量高价值的创意 而剩下的却如一潭死水般无法产出分毫创意 造成此等差距的原因究竟是什么 液态网络这个词 是由创新者史蒂文 约翰逊 Stev

  • iptables 命令

    NAME iptables administration tool for IPv4 packet filtering and NAT SYNOPSIS iptables ADC 指定链的规则 A 添加 D 删除 C 修改 iptables

  • 【Neo4j】第 4 章：图形数据科学Library and Path Finding

    大家好 我是Sonhhxg 柒 希望你看完之后 能对你有所帮助 不足请指正 共同学习交流 个人主页 Sonhhxg 柒的博客 CSDN博客 欢迎各位 点赞 收藏 留言 系列专栏 机器学习 ML 自然语言处理 NLP 深度学习 DL fore

  • Java RMI 入门

    Java RMI 入门 如何通信 实战 完整代码 Java RMI 指 JDK 内置的关于实现远程方法调用 Remote Method Invocation 的 API 这些 API 位于包 java rmi 中 通过 Java RMI 可

  • java事件监听机制（观察者设计模式的实际运用）

    package cn yang test controller java的事件监听机制和观察者设计模式 Created by Dev yang on 2016 3 1 public class Demo public static void

  • QT-MQTT客户端和服务端介绍

    MQTT Message Queuing Telemetry Transport 是一种基于发布 订阅模式的消息传递协议 在QT中使用MQTT 可以轻松地创建MQTT客户端和服务端 并实现设备之间的通信 在QT中 可以使用Qt MQTT模块

  • 7个Python有趣的lambda应用

    7个Python有趣的lambda应用 1 排序sort 2 寻找最大值max 3 查找最小值min 4 filter 5 map 6 reduce 7 Sorted 源码 1 排序sort 2 寻找最大值max 3 查找最小值min 4

  • javascript数据验证

    校验是否全由数字组成 function isDigit s var patrn 0 9 1 20 if patrn exec s return false return true 校验登录名 只能输入5 20个以字母开头 可带数字 的字串

  • 2021美赛E题

    2021年 问题E 重新优化食物系统 最近的事件向我们表明 我们的全球粮食系统即使在世界的某些地区也是不稳定的 它通常服务于全世界 这些不稳定的部分原因是我们目前的全球气候变化 庞大的国内和国际食品生产商和经销商体系 这个食物系统 使食物的

  • 2022-15-Java 设计模式-抽象工厂模式

    在工厂方法模式中 我们使用一个工厂创建一个产品 一个具体工厂对应一个具体产品 但有时候我们需要一个工厂能够提供多个产品对象 而不是单一的对象 这个时候我们就需要使用抽象工厂模式 在介绍抽象工厂模式前 我们先厘清两个概念 产品等级结构 产品等

  • 【Java书笔记】：《Redis 深度历险：核心原理和应用实践》分布式锁，延时队列，位图，HyperLogLog，布隆过滤器，漏斗限流，GeoHash，Scan，管道，事务，主从，Redis源码

    Redis 深度历险 核心原理和应用实践 目 录 开篇 授人以鱼不若授人以渔 Redis 可以用来做什么 7 由 Redis 面试想到的 7 小册的内容范围 8 Redis 可以做什么 8 基础 万丈高楼平地起 Redis 基础数据结构 1

  • 备战数学建模34-BP神经网络预测2

    目录 一 辛烷值的预测 1 题目分析与原理介绍 2 神经网络建立过程 3 预测结果分析 BP神经网络模型 包含输入层 隐含层和输出层 正向传播过程是通过输入样本到输入层 通过输入层经过各层隐藏层 最后到达输出层 若输出层输出值与期望值的输出

  • STM32学习----通用定时器的应用（输入捕获，测量周期和占空比）

    输入捕获的应用 输入捕获一般是用来测量输入信号的频率 占空比这些信息 输入捕获的原理 捕获的原理 1 信号从某个通道输入 比如通道1 CH1 2 经过滤波和边沿检测后产生两个一模一样的信号TI1FP1和TI1FP2 TI1FP1送给捕获通道

  • 身份证二进制数据解析

    头数据 AA AA AA 96 69 05 08 00 00 90 01 00 04 00 文本信息 256个字节 使用Unicode解码 得到中文信息 姓名 30个字节 性别 2个字节 民族 4个字节 出生日期 16个字节 地址 70个字

  • 数据治理项目工作方式总结

    1 当工作完成后 每天完成对应的计划任务列表分析 图表展示 代码展示等汇总报告 PPT 是简单的方式 word excel也是可以的 这边习惯用word 写一写文档之类的 excel 做工作拆分和总结 PPT 做工作汇报 2 没有的话 可以

  • 入门数据结构，c语言实现循环队列实现（详细篇）。

    目录 一 前言 二 循环队列的概念 三 实现循环队列 1 头文件与特殊函数介绍 2 循环队列的结构体 3 队列的初始化 4 判断队列是否为空 5 队列的进队操作 6 队列的出队操作 7 返回队头 8 返回队列长度 9 放回队列容量大小 10

热门标签