入门数据结构,c语言实现循环队列实现(详细篇)。

这篇具有很好参考价值的文章主要介绍了入门数据结构,c语言实现循环队列实现(详细篇)。。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、前言

二、循环队列的概念

三、实现循环队列

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

2、循环队列的结构体

3、队列的初始化

4、判断队列是否为空

5、队列的进队操作

6、队列的出队操作

7、返回队头

8、返回队列长度

9、放回队列容量大小

10、销毁队列

四、完成队列(队列完整代码)

五、结束语


一、前言

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

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

二、循环队列的概念

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

循环队列c语言,数据结构,c语言

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

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

三、实现循环队列

注意:为了好理解,之后出现的队列是循环队列的意思

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;
}

结果:

循环队列c语言,数据结构,c语言

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

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;
}

结果:

循环队列c语言,数据结构,c语言

指向动态创建数组的指针(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是我们循环队列的关键,我们看图理解。

循环队列c语言,数据结构,c语言

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

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

循环队列c语言,数据结构,c语言

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

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

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

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.如图:

循环队列c语言,数据结构,c语言

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

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

2.如图:

循环队列c语言,数据结构,c语言

当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;
}

五、结束语

写完后,发现写的有点长,哈哈哈!!回头看了看,发现有一些地方有点啰嗦,想把她们删掉,但再三考虑后还是没有删,如果能看到这里,真的是非常感谢,如果哪有疑问或本章哪个位置出来了错误或者有什么建议,可以在评论区进行评论,感觉支持!文章来源地址https://www.toymoban.com/news/detail-735896.html

到了这里,关于入门数据结构,c语言实现循环队列实现(详细篇)。的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——循环队列的实现

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可以写在评论区或者私信

    2024年03月24日
    浏览(41)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、

    2024年01月20日
    浏览(43)
  • Java 数据结构篇-用链表、数组实现队列(数组实现:循环队列)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 队列的说明         1.1 队列的几种常用操作         2.0 使用链表实现队列说明         2.1 链表实现队列         2.2 链表实现队列 - 入栈操作         2.3 链表实现队

    2024年02月05日
    浏览(38)
  • 【数据结构】队列的使用|模拟实现|循环队列|双端队列|面试题

    1.1 概念 队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为 队尾(Tail/Rear) 出队列:进行删除操作的一端称为 队头(Head/Front) 队列和栈的区别: 队列是 先进先出(队

    2024年02月03日
    浏览(43)
  • 【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路: 🍊数据结构: 使用数组为数据结构,且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(38)
  • 探索数据结构:链式队与循环队列的模拟、实现与应用

    队列(queue)是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表。其严格遵循 先进先出(First In First Out) 的规则,简称 FIFO 。 队头(Front) :允许删除的一端,又称队首。 队尾(Rear) :允许插入的一端。 队列与栈类似,实现方式有两种。一种是以 数组

    2024年04月08日
    浏览(82)
  • 数据结构:队列(Python语言实现)

    队列是一种 先进先出 的数据结构(特殊的线性结构),在队列 尾部 插入新元素,在队列 头部 删除元素。 一般队列的基本操作如下: create:创建空队列。 enqueue:将新元素加入队列的尾部,返回新队列。 dequeue:删除队列头部元素,返回新队列。 front:返回队列头部的元素

    2024年02月13日
    浏览(45)
  • 数据结构——队列(C语言实现)

    队列是一种特殊的线性结构,数据只能在一端插入,数据也只能在另一端进行删除。插入数据的那一端称之为队尾,插入数据的动作称之为入队。删除数据的那一端称之为队头,删除数据的动作称之为出列。队列遵守的是FIFO原则(Frist In First Out),即先进先出原则。 队列具

    2024年02月03日
    浏览(77)
  • 数据结构 队列(C语言实现)

            任其事必图其效;欲责其效,必尽其方。——欧阳修;本篇文章主要写的是什么是队列、以及队列是由什么组成的和这些组成接口的代码实现过程。( 大多细节的实现过程以注释的方式展示请注意查看 )    话不多说安全带系好,发车啦 (建议电脑观看) 。 附

    2024年02月11日
    浏览(52)
  • C语言实现队列--数据结构

    😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️Take your time ! 😶‍🌫️😶‍🌫️😶‍🌫️😶‍🌫️ 💥个人主页:🔥🔥🔥大魔王🔥🔥🔥 💥所属专栏:🔥魔王的修炼之路–数据结构🔥 如果你觉得这篇文章对你有帮助,请在文章结尾处留下你的 点赞 👍和 关注 💖,支持一

    2024年02月05日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包