devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：从前慢现在也慢 | 2024-04-12 21:04:54

赞

踩

c语言循环队列

目录

一、前言

二、循环队列的概念

三、实现循环队列

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

2、循环队列的结构体

3、队列的初始化

4、判断队列是否为空

5、队列的进队操作

6、队列的出队操作

7、返回队头

8、返回队列长度

9、放回队列容量大小

10、销毁队列

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

五、结束语

一、前言

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

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

二、循环队列的概念

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

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

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

三、实现循环队列

注意：为了好理解，之后出现的队列是循环队列的意思。

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

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>

本次队列需要的头文件。

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

例：

  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <math.h>
  4.  
  5. int main(void)
  6. {
  7.     double x = -1.0;
  8.     assert(x >= 0.0);
  9.     printf("sqrt(x) = %f\n", sqrt(x));   
  10.  
  11.     return 0;
  12. }

结果：

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

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

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

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

例：

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

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

2、循环队列的结构体

  1. typedef void queue;
  2.  
  3. typedef struct Tag_Queue {
  4. 	int* m; //指向动态创建数组的指针
  5. 	int front; //队列的头下标
  6. 	int rear; //队列的尾下标
  7. 	int capacity; //队列的容量大小
  8. }Tag_Queue;

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

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

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

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

如：

  1. #include<stdio.h>
  2. int main(void)
  3. {
  4.     int x = 123;
  5.     int* p = &x;
  6.     void* test = p;
  7.     
  8.     int* p2 = (int*)test; //进行强制转换赋值
  9.  
  10.     printf("%d\n", *p2); //访问p指向地址的数据，即p指向地址的数据
  11.  
  12.     return 0;
  13. }

结果：

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

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

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

3、队列的初始化

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

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

  1. queue* Queue_init(int number = 0) { //可以默认初始化
  2. 	assert(number >= 0); //队列大小至少为0
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)malloc(sizeof(Tag_Queue)); //创建队列
  5. 	if (ret == NULL) { //检查队列是否创建成功
  6. 		printf("ret == NULL\n");
  7. 		exit(1);
  8. 	}
  9. 	ret->m = (int*)calloc((size_t)number + (size_t)1, sizeof(int)); //创建数组
  10. 	if (ret == NULL) { //检查数组是否创建成功
  11. 		printf("ret->m == NULL\n");
  12. 		exit(1);
  13. 	}
  14.  
  15. 	ret->front = 0;
  16. 	ret->rear = 0;
  17. 	ret->capacity = number;
  18.  
  19. 	return ret;
  20. }
  21. ​

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、判断队列是否为空

  1. int Queue_empty(queue* q) {
  2. 	assert(q != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)q; //进行强制转换，使后续可以操作队列
  5.  
  6. 	if (ret->front == ret->tail) {
  7. 		return 1;
  8. 	}
  9. 	else {
  10. 		return 0;
  11. 	}
  12. }
  13. ​/*返回值：1 此队列为空
  14.          0 此队列不空*/
  15.

5、队列的进队操作

  1. ​void Queue_push(queue* q, int size) {
  2. 	assert(q != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)q; //进行强制转换，使后需可以操作队列
  5.  
  6. 	if ((ret->rear + 1) % ret->capacity == ret->front) {
  7. 		int* temp = (int*)realloc(ret->m, sizeof(int) * ((size_t)ret->capacity + (size_t)16));
  8. 		if (temp == NULL) {
  9. 			printf("temp == NULL\n");
  10. 			exit(1);
  11. 		}
  12.  
  13. 		ret->m = temp;
  14. 		ret->capacity = ret->capacity + 16;
  15. 	}
  16.  
  17. 	ret->m[ret->rear] = size; //进队
  18. 	ret->rear = (ret->rear + 1) % ret->capacity; //尾下标向前移动一位，%capacity防止下标越界
  19.  
  20. 	return;
  21. }

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

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

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

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

6、队列的出队操作

  1. void Queue_pop(queue* p) {
  2. 	assert(p != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列
  5.  
  6. 	if (Queue_empty(p) == 1) { //调用Queue_empty判断队列是否为空，若为空终止程序
  7. 		exit(1);
  8. 	}
  9.  
  10. 	ret->front = (ret->front + 1) % ret->capacity; //出队后，队头下标往前移动， %capacity防止下标溢出
  11.  
  12. 	return;
  13. }

7、返回队头

  1. int Queue_top(queue* p) {
  2. 	assert(p != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列
  5.  
  6. 	if (Queue_empty(ret) == 1) { //调用Queue_empty判断队列是否为空， 若为空终止程序
  7. 		printf("Queue = empty\n");
  8. 		exit(1);
  9. 	}
  10.  
  11. 	return ret->m[ret->front]; //返回队头数据
  12. }

8、返回队列长度

  1. int Queue_size(queue* p) {
  2. 	assert(p != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列
  5.  
  6. 	return (ret->tail - ret->front + ret->capacity) % ret->capacity;
  7. }

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

1.如图：

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

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

2.如图：

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

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

9、放回队列容量大小

  1. int Queue_capacity(queue* p) {
  2. 	assert(p != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)p; //进行强制转换，使后续可以操作队列
  5.  
  6. 	return ret->capacity;
  7. }

10、销毁队列

  1. void Queue_clear(queue**p) { //利用二级指针，控制指针
  2. 	assert(p != NULL); //判断队列是否存在
  3.  
  4. 	Tag_Queue* ret = (Tag_Queue*)*p; //进行强制转换，使后续可以操作队列
  5.  
  6. 	free(ret->m); //将数组进行销毁
  7. 	free(ret); //将队列结构体进行销毁
  8.  
  9. 	*p = NULL; //将指针指向NULL，防止成为野指针
  10.  
  11. 	return;
  12. }

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

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>
  4.  
  5. typedef void queue;
  6.  
  7. typedef struct Tag_Queue {
  8. 	int* m;
  9. 	int front;
  10. 	int tail;
  11. 	int capacity;
  12. }Tag_Queue;
  13.  
  14. queue* Queue_init(int number = 0) {
  15. 	assert(number >= 0);
  16.  
  17. 	Tag_Queue* ret = (Tag_Queue*)malloc(sizeof(Tag_Queue));
  18. 	if (ret == NULL) {
  19. 		printf("ret == NULL\n");
  20. 		exit(1);
  21. 	}
  22. 	ret->m = (int*)calloc((size_t)number + (size_t)1, sizeof(int));
  23. 	if (ret == NULL) {
  24. 		printf("ret->m == NULL\n");
  25. 		exit(1);
  26. 	}
  27.  
  28. 	ret->front = 0;
  29. 	ret->tail = 0;
  30. 	ret->capacity = number;
  31.  
  32. 	return ret;
  33. }
  34.  
  35. int Queue_empty(queue* q) {
  36. 	assert(q != NULL);
  37.  
  38. 	Tag_Queue* ret = (Tag_Queue*)q;
  39.  
  40. 	if (ret->front == ret->tail) {
  41. 		return 1;
  42. 	}
  43. 	else {
  44. 		return 0;
  45. 	}
  46. }
  47.  
  48. void Queue_push(queue* q, int size) {
  49. 	assert(q != NULL);
  50.  
  51. 	Tag_Queue* ret = (Tag_Queue*)q;
  52.  
  53. 	if ((ret->tail + 1) % ret->capacity == ret->front) {
  54. 		int* temp = (int*)realloc(ret->m, sizeof(int) * ((size_t)ret->capacity + (size_t)16));
  55. 		if (temp == NULL) {
  56. 			printf("temp == NULL\n");
  57. 			exit(1);
  58. 		}
  59.  
  60. 		ret->m = temp;
  61. 		ret->capacity = ret->capacity + 16;
  62. 	}
  63.  
  64. 	ret->m[ret->tail] = size;
  65. 	ret->tail = (ret->tail + 1) % ret->capacity;
  66.  
  67. 	return;
  68. }
  69.  
  70. int Queue_top(queue* p) {
  71. 	assert(p != NULL);
  72.  
  73. 	Tag_Queue* ret = (Tag_Queue*)p;
  74.  
  75. 	if (Queue_empty(ret) == 1) {
  76. 		printf("Queue = empty\n");
  77. 		exit(1);
  78. 	}
  79.  
  80. 	return ret->m[ret->front];
  81. }
  82.  
  83. void Queue_pop(queue* p) {
  84. 	assert(p != NULL);
  85.  
  86. 	Tag_Queue* ret = (Tag_Queue*)p;
  87.  
  88. 	if (Queue_empty(p) == 1) {
  89. 		exit(1);
  90. 	}
  91.  
  92. 	ret->front = (ret->front + 1) % ret->capacity;
  93.  
  94. 	return;
  95. }
  96.  
  97. int Queue_size(queue* p) {
  98. 	assert(p != NULL);
  99.  
  100. 	Tag_Queue* ret = (Tag_Queue*)p;
  101.  
  102. 	return (ret->tail - ret->front + ret->capacity) % ret->capacity;
  103. }
  104.  
  105. int Queue_capacity(queue* p) {
  106. 	assert(p != NULL);
  107.  
  108. 	Tag_Queue* ret = (Tag_Queue*)p;
  109.  
  110. 	return ret->capacity;
  111. }
  112. void Queue_clear(queue**p) {
  113. 	assert(p != NULL);
  114.  
  115. 	Tag_Queue* ret = (Tag_Queue*)*p;
  116.  
  117. 	free(ret->m);
  118. 	free(ret);
  119.  
  120. 	*p = NULL;
  121.  
  122. 	return;
  123. }

五、结束语

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/412708
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号