devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

详解循环队列_循环队列front和rear

作者：笔触狂放9 | 2024-04-12 21:09:54

赞

踩

循环队列front和rear

一.定义

循环队列是一种队列数据结构，由固定大小的数组组成，其中包括两指针，"front" 和 "rear"，以管理队列元素。其特点在于队列具有循环性质，即在"rear"指针达到数组末尾时，下一个元素将从数组开头插入。它支持高效的入队和出队操作，能判断队列的空和满状态，通常应用于需要周期性循环存储数据的场景。

二.特点

  1. 固定大小的数组：循环队列使用固定大小的数组来存储元素。这个数组的大小在创建队列时就确定，通常不会动态扩展或缩小。

  2. 循环性质：循环队列的一个关键特点是它的队列是循环的。当"rear"指针到达数组的末尾时，下一个元素将从数组的开头插入。这意味着队列可以循环利用数组的空间，避免了数组满了之后无法插入新元素的问题。

  3. 双指针：循环队列使用两个指针，分别是"front"（前指针）和"rear"（后指针）。"front"指针指向队列的第一个元素，"rear"指针指向队列的最后一个元素。这些指针的位置关系可以用来判断队列的状态（空或满）以及执行入队和出队操作。

  4. 高效的入队和出队操作：由于循环队列的特性，入队和出队操作通常非常高效。入队操作只需在"rear"指针指向的位置插入元素并移动"rear"指针，出队操作只需移除"front"指针指向的元素并移动"front"指针。这些操作的时间复杂度通常是O(1)。

  5. 判空和判满：循环队列有两种状态，即空队列和满队列。你可以使用指针的位置关系来判断队列是否为空（"front" == "rear"）或满（("rear" + 1) % 数组大小 == "front"）。

  6. 有限大小：由于数组大小是固定的，循环队列的容量有限。这意味着在队列满时，无法再插入更多元素，除非出队一些元素来腾出空间。

  7. 适用于环形数据存储需求：循环队列通常用于需要周期性地循环存储数据的应用场景，如缓冲区管理、任务调度等。

  8. 需要小心管理大小和元素数量：由于固定的容量，循环队列需要小心管理队列的大小和元素数量，以避免数据溢出或元素丢失的问题。

总之，循环队列是一种高效的队列数据结构，适用于需要快速入队和出队操作的情况，但需要谨慎处理队列的大小和元素数量以确保正常运作。

三.基本运算

  1. 初始化：创建一个循环队列时，需要初始化队列的数组大小，以及"front" 和 "rear" 指针的初始位置。通常，"front" 和 "rear" 初始化为相同的值，表示空队列。

  2. 入队操作：入队操作用于将元素添加到队列中。这包括将元素插入到"rear"指针所指向的位置，然后将"rear"指针向后移动。如果队列已满（即"rear" + 1 等于 "front"，考虑循环性质），则入队操作失败。

  3. 出队操作：出队操作用于移除队列中的元素。这包括从"front"指针所指向的位置移除元素，然后将"front"指针向后移动。如果队列为空（即"front" 和 "rear" 指向相同位置），则出队操作失败。

  4. 判空和判满：通过检查"front" 和 "rear" 指针的位置关系，可以判断队列是否为空（"front" == "rear"）或满（("rear" + 1) % 数组大小 == "front"，考虑循环性质）。

  5. 获取队列大小：可以通过计算"rear"和"front"指针的位置关系来获取队列中元素的数量。

这些是循环队列的基本运算，它们使队列能够高效地支持元素的插入和删除，并提供了对队列状态的判断。循环队列的特点在于可以循环利用数组的空间，从而更有效地管理队列中的元素。

四.代码实现

1.定义接口

  1. #define MAXSIZE 100
  2.  
  3. typedef int DataType;
  4.  
  5. typedef struct
  6. {
  7. 	DataType data[MAXSIZE];
  8. 	int front;
  9. 	int rear;
  10. }CirclesQueue;
  11.  
  12. /*循环队列初始化*/
  13. int init(CirclesQueue *Q);
  14.  
  15. /*入队*/
  16. int enqueue(CirclesQueue *Q, DataType x);
  17.  
  18. /*队满*/
  19. int isfull(CirclesQueue *Q);
  20.  
  21. /*出队*/
  22. int dequeue(CirclesQueue *Q, DataType *);
  23.  
  24. /*队空*/
  25. int isempty(CirclesQueue *Q);
  26.  
  27. // 输出队列内容  
  28. void printQueue(CirclesQueue *Q);
  29.  
  30. // 获取队列长度  
  31. int getLength(CirclesQueue *Q);
  32.  
  33. // 获取队首元素
  34. DataType getFront(CirclesQueue* Q);

2.初始化

  1. /*循环队列初始化*/
  2. int init(CirclesQueue *Q)
  3. {
  4. 	Q->front = Q->rear = 0;
  5. 	return 0;
  6. }

3.入队

  1. /*入队*/
  2. int enqueue(CirclesQueue *Q, DataType x)
  3. {
  4. 	if(isfull(Q))
  5. 	{
  6. 		printf("队列已满！100001\n");
  7. 		return 100001;
  8. 	}
  9.  
  10. 	Q->rear = (Q->rear+1) % MAXSIZE;
  11. 	Q->data[Q->rear] = x;
  12. 	return 0;
  13. }

4.队满

  1. /*队满*/
  2. int isfull(CirclesQueue *Q)
  3. {
  4. 	return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
  5. }

5.出队

  1. /*出队*/
  2. int dequeue(CirclesQueue *Q, DataType *x)
  3. {
  4. 	if(isempty(Q))
  5. 	{
  6. 		printf("队列为空！100002\n");
  7. 		return 100002;
  8. 	}
  9. 	Q->front = (Q->front+1) % MAXSIZE;
  10. 	*x = Q->data[Q->front];
  11. 	return 0;
  12. }

6.队空

  1. /*队空*/
  2. int isempty(CirclesQueue *Q)
  3. {
  4. 	return (Q->front == Q->rear) ? 1 : 0;
  5. }

7.输出队列内容

  1. // 输出队列内容  
  2. void printQueue(CirclesQueue *Q) {
  3.     int i;
  4.     if (isempty(Q)) {  
  5.         printf("Queue is empty.\n");  
  6.         return;  
  7.     }  
  8.     i = (Q -> front) %MAXSIZE;
  9.     do{
  10.         printf(" %d",Q -> data[(i + 1 % MAXSIZE)]);
  11.         i = (i+1) %MAXSIZE;
  12.     }while(i != Q -> rear);
  13. }

8.获取队列长度

  1. // 获取队列长度  
  2. int getLength(CirclesQueue *Q) {  
  3.     return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; // 循环队列：若rear在前方，则长度为rear-front+MAXSIZE，否则为rear-front  
  4. }

9.获取队首元素

  1. // 获取队首元素  
  2. DataType getFront(CirclesQueue* Q) {  
  3.     int i;
  4.     i = (Q -> front) %MAXSIZE;
  5.     return Q -> data[(i + 1 % MAXSIZE)];
  6. }

五.运行截图

 六.完整代码

1.CirclesQueue.h
  1. #define MAXSIZE 100
  2.  
  3. typedef int DataType;
  4.  
  5. typedef struct
  6. {
  7. 	DataType data[MAXSIZE];
  8. 	int front;
  9. 	int rear;
  10. }CirclesQueue;
  11.  
  12. /*循环队列初始化*/
  13. int init(CirclesQueue *Q);
  14.  
  15. /*入队*/
  16. int enqueue(CirclesQueue *Q, DataType x);
  17.  
  18. /*队满*/
  19. int isfull(CirclesQueue *Q);
  20.  
  21. /*出队*/
  22. int dequeue(CirclesQueue *Q, DataType *);
  23.  
  24. /*队空*/
  25. int isempty(CirclesQueue *Q);
  26.  
  27. // 输出队列内容  
  28. void printQueue(CirclesQueue *Q);
  29.  
  30. // 获取队列长度  
  31. int getLength(CirclesQueue *Q);
  32.  
  33. // 获取队首元素
  34. DataType getFront(CirclesQueue* Q);
2.CirclesQueue.c
  1. #include <stdio.h>
  2. #include "CirclesQueue.h"
  3.  
  4. /*循环队列初始化*/
  5. int init(CirclesQueue *Q)
  6. {
  7. 	Q->front = Q->rear = 0;
  8. 	return 0;
  9. }
  10.  
  11.  
  12. /*入队*/
  13. int enqueue(CirclesQueue *Q, DataType x)
  14. {
  15. 	if(isfull(Q))
  16. 	{
  17. 		printf("队列已满！100001\n");
  18. 		return 100001;
  19. 	}
  20.  
  21. 	Q->rear = (Q->rear+1) % MAXSIZE;
  22. 	Q->data[Q->rear] = x;
  23. 	return 0;
  24. }
  25.  
  26. /*队满*/
  27. int isfull(CirclesQueue *Q)
  28. {
  29. 	return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
  30. }
  31.  
  32.  
  33. /*出队*/
  34. int dequeue(CirclesQueue *Q, DataType *x)
  35. {
  36. 	if(isempty(Q))
  37. 	{
  38. 		printf("队列为空！100002\n");
  39. 		return 100002;
  40. 	}
  41. 	Q->front = (Q->front+1) % MAXSIZE;
  42. 	*x = Q->data[Q->front];
  43. 	return 0;
  44. }
  45.  
  46. /*队空*/
  47. int isempty(CirclesQueue *Q)
  48. {
  49. 	return (Q->front == Q->rear) ? 1 : 0;
  50. }
  51.  
  52. // 输出队列内容  
  53. void printQueue(CirclesQueue *Q) {
  54.     int i;
  55.     if (isempty(Q)) {  
  56.         printf("Queue is empty.\n");  
  57.         return;  
  58.     }  
  59.     i = (Q -> front) %MAXSIZE;
  60.     do{
  61.         printf(" %d",Q -> data[(i + 1 % MAXSIZE)]);
  62.         i = (i+1) %MAXSIZE;
  63.     }while(i != Q -> rear);
  64. }
  65.  
  66. // 获取队列长度  
  67. int getLength(CirclesQueue *Q) {  
  68.     return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; // 循环队列：若rear在前方，则长度为rear-front+MAXSIZE，否则为rear-front  
  69. } 
  70.  
  71. // 获取队首元素  
  72. DataType getFront(CirclesQueue* Q) {  
  73.     int i;
  74.     i = (Q -> front) %MAXSIZE;
  75.     return Q -> data[(i + 1 % MAXSIZE)];
  76. }
3.main.c
  1. #include <stdio.h>
  2. #include "CirclesQueue.h"
  3. #include <string.h>
  4. #include <stdlib.h>
  5.  
  6. int main(int argc, char* argv[])
  7. {
  8. 	CirclesQueue Q;
  9. 	DataType x;
  10. 	int cmd;
  11. 	char yn;
  12. int result;
  13.     char welcome[] = "欢迎使用";
  14. 	int i = 0; 
  15. 	int m = 0; 
  16. 	int n = 0;
  17.     for(i=0;i<strlen(welcome);i++)
  18. 	{
  19. 		printf("%c",welcome[i]);
  20. 		for(m=0;m<10000;m++)
  21. 			for(n=0;n<1000;n++)
  22. 			{
  23. 				;
  24. 			}
  25. 	}
  26. 	printf("\n\n\n");
  27.  
  28. 	do
  29. 	{	
  30. 		printf("-----------循环队列演示-----------\n");
  31. 		printf(" 1. 初始化\n");
  32. 		printf(" 2. 入队\n");
  33. 		printf(" 3. 出队\n");
  34. 		printf(" 4. 队空\n");
  35. 		printf(" 5. 队满\n");
  36. 		printf(" 6. 队列元素个数\n");
  37. 		printf(" 7. 取队首元素\n");
  38. 		printf(" 8. 输出队列\n");
  39. 		printf(" 9. 帮助\n");
  40. 		printf(" 0. 退出\n");
  41. 		printf(" 请选择（0~6）：");
  42. 		scanf("%d",&cmd);
  43. 		switch(cmd)
  44. 		{
  45. 		case 1:
  46. 			init(&Q);
  47. 			printf("队列已初始化！\n");
  48. 			break;
  49. 		case 2:
  50. 			printf("请输入要入队的元素x=");
  51. 			scanf("%d", &x);
  52. 			if(!enqueue(&Q,x))
  53. 			{
  54. 				printf("元素x=%d已入队\n", x);
  55. 			}
  56. 			break;
  57. 		case 3:
  58. 			printf("确定要出队（出队会将删除对首元素, y or n, n）？");
  59. 			getchar();
  60. 			scanf("%c", &yn);
  61.  
  62. 			if(yn == 'y' || yn == 'Y')
  63. 			{
  64. 				if(!dequeue(&Q,&x))
  65. 				{
  66. 					printf("队首元素【%d】已出队！\n", x);
  67. 				}
  68. 			}
  69. 			break;
  70. 	    case 4:
  71. 			if(isempty(&Q)) printf("队列为空！\n");
  72. 			else printf("队列不为空！\n");
  73. 			break;
  74. 		case 5:
  75. 			if(isfull(&Q)) printf("队列已满！\n");
  76. 			else printf("队列还没有满！\n");
  77. 			break;
  78. 		case 6:
  79. 			printf("队列的长度：%d\n",getLength(&Q));
  80. 			break;
  81. 		case 7:
  82. 		    printf("队列首元素: %d\n", getFront(&Q));  
  83.             break;
  84. 		case 8:
  85. 			printf("输出队列：");
  86. 			printQueue(&Q);
  87. 			printf("\n");
  88. 			break;
  89. 		case 9:
  90. 		    printf("本程序由邵毅豪设计开发\n");
  91. 		    break;
  92. 		}
  93.  
  94. 	}while(cmd!=0);
  95.  
  96.  
  97. 	return 0;
  98. }

七.小结

循环队列是一种基于数组的队列数据结构，具有以下关键特点和操作：

  1. 固定大小的数组：循环队列使用固定大小的数组来存储元素，该大小在创建队列时确定。

  2. 循环性质：队列的关键特点是它是循环的，即当"rear"指针到达数组末尾时，下一个元素将从数组的开头插入，使得队列可以循环利用数组空间，避免了数组满了之后无法插入新元素的问题。

  3. 双指针：循环队列使用两指针，"front"（前指针）和 "rear"（后指针），分别指向队列的第一个元素和最后一个元素。

  4. 高效的入队和出队操作：由于循环队列的特性，入队和出队操作通常是高效的，时间复杂度通常是O(1)。

  5. 判空和判满：可以通过指针位置的关系判断队列是否为空（"front" == "rear"）或满（("rear" + 1) % 数组大小 == "front"）。

  6. 有限大小：由于数组大小是固定的，循环队列的容量有限，因此在队列满时，无法再插入更多元素，除非出队一些元素来腾出空间。

  7. 适用场景：循环队列通常用于需要周期性循环存储数据的应用场景，如缓冲区管理、任务调度等。

  8. 需要小心管理大小和元素数量：由于容量固定，循环队列需要小心管理队列的大小和元素数量，以避免数据溢出或元素丢失的问题。

总之，循环队列是一种高效的队列数据结构，适用于需要快速入队和出队操作的情况，但要小心处理队列的大小和元素数量，以确保正常运作。

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

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

  

闽ICP备14008679号