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

数据结构——循环队列【c语言版】_写出循环队列数据元素类型为字

作者：Monodyee | 2024-04-10 17:05:19

赞

踩

写出循环队列数据元素类型为字

 队列（quque）简称队，只允许在表的一端输入，在表的另一端删除(操作受限制的线性表)，

把进行插入的一段叫做队尾（表尾），把进入删除的一端叫做队首或队头（表头）。

队列最主要的特点：先进先出，FIFO（first in first out）

队列有其实有三种：顺序队列、 循环队列、链式队列

       为了避免顺序队列中出现的假溢出现象，我们只需要把数组的前后端连接起来，形成一个环形数组，在逻辑上把这个环称为环形队列或者循环队列。

        下面是循环队列的实现过程：

        假设栈的元素个数最大不超过正整数MAXSIZE，所以元素具有同一数据类型（ElemType），用下来方式来声明循环队列的类型SQQueue：

  1. #define MAXSIZE 10  //队列的最大容量
  2.  
  3. typedef int ElemType;  //队列中元素类型
  4.  
  5. typedef struct
  6. {
  7. 	ElemType data[MAXSIZE];//存储值 
  8. 	int front;//存储队头元素前一个单元的下标 
  9. 	int rear;//存储队尾元素的下标 
  10. }SQQueue;

对于循环队列来说，有以下四个非常重要的要素：

        1.队空条件：SQ->front == SQ->rear 

        2.队满条件：SQ->rear+1)%MAXSIZE == SQ->front

        3.进队操作：

                            SQ->rear = (SQ->rear + 1) % MAXSIZE;
                            SQ->data[SQ->rear] = e;                           

                            先将 SQ->rear = (SQ->rear + 1) % MAXSIZE，再将元素e放在rear指向的位置

        4.出队操作：

                            SQ->front = (SQ->front+1) % MAXSIZE;
                            *e = SQ->data[SQ->front];

                             先将 SQ->front = (SQ->front+1) % MAXSIZE，再将取出front指向的位置上的元                               素并存放于e中

1）队列初始化

        构造一个空的队列SQ，将front和rear指针都指向-1，代码如下：

  1. void InitQueue(SQQueue* SQ)
  2. {
  3. 	SQ->front = SQ->rear = -1;	
  4. 	
  5. }

2)判断队列是否为空

        注：为了区分空和满，任意时候都预留1个单元出来x的下一个：(x+1)%MAXSIZE

        循环队列中，判断队列是否为空，只需要判断SQ->front == SQ->rear的条件成立即可，代码如下：

  1. //判断队列为空
  2.  
  3. void InitQueue(SQQueue* SQ)
  4. {
  5. 	SQ->front = SQ->rear = -1;	
  6. 	
  7. }

3）判断队列是否为满

                循环队列中，判断队列是否为满，只需要判断(SQ->rear+1)%MAXSIZE == SQ->front的条件成立即可，

特别注意，循环队列中的特殊情况，初始状态下SQ->front == -1,当执行进队操作SQ->rear == MAXSIZE - 2时队列已满，需要将这一特殊情况考虑，代码如下：

  1. int IsFUll(SQQueue* SQ)  //判断队列是否为满 
  2. {	
  3. 	 //尾指针+1追上队头指针，标志队列已经满了
  4. 	if(((SQ->rear+1)%MAXSIZE == SQ->front)||(SQ->rear==MAXSIZE-2&&SQ->front==-1))
  5. 	{
  6. 		return 1;
  7. 	}
  8. 	return 0; //队不满 
  9. }

4）入队

        在队列不满条件下先将rear+1，再将元素e放在rear指向的位置，因此该操作需要先判断操作合法性，若队列未满，执行相关操作，否则提示并返回0，这里可以调用IsFull(SQQueue* SQ)来判断,代码如下：

  1.  
  2. int EnterQueue(SQQueue* SQ,ElemType e)
  3. {
  4. 	if (IsFUll(SQ))  // (SQ->rear + 1)%MAXSIZE == SQ->front
  5. 	{
  6. 		printf("队满，不能进队。\n"); 
  7. 		return 0;
  8. 	}
  9. 	SQ->rear = (SQ->rear + 1) % MAXSIZE;
  10. 	SQ->data[SQ->rear] = e;
  11. }

5)出队

         这里需要先判断循环队列是否为空，若为空，提示并返回0，若不空则执行相关操作，         先将 SQ->front = (SQ->front+1) % MAXSIZE，再将取出front指向的位置上的元 素并存放于e中,这里可以调用IsEmpty(SQQueue* SQ)来判断，代码如下：

  1. int DeleteQueue(SQQueue* SQ,ElemType* e)
  2. {
  3. 	if (IsEmpty(SQ))
  4. 	{
  5. 		printf("队空，不能出队！\n");
  6. 		return 0;
  7. 	}
  8. 	SQ->front = (SQ->front+1) % MAXSIZE;
  9. 	*e = SQ->data[SQ->front];
  10. }

6)求队列长度

代码如下：

  1. int lenghtSQQueue(SQQueue* SQ)
  2. {
  3. 	int len;
  4. 	len = 0;
  5. 	len = (SQ->rear-SQ->front+MAXSIZE)%MAXSIZE;	
  6. 	return len;
  7. }

7）打印队列中的元素

        从队首到队尾，代码如下：

  1. //打印队列中的与元素
  2.  
  3. void DispSQQueue(SQQueue* SQ)
  4. {
  5. 	if (IsEmpty(SQ))
  6. 	{
  7. 		printf("队空！");
  8. 	}
  9. 	int i;
  10. 	i = SQ->front+1;
  11. 	printf("队列元素为：");
  12. 	while(i <= SQ->rear)
  13. 	{
  14. 		
  15. 		printf("%d ",SQ->data[i]); 
  16. 		i++;
  17. 	}
  18. }

下面是入队、出栈和返回队列长度以及打印出队列元素的操作：

  1. int main()
  2. {
  3. 	SQQueue SQ;
  4. 	ElemType e;
  5. 	InitQueue(&SQ);
  6. 	
  7. 	//入队
  8. 	EnterQueue(&SQ,1);
  9. 	EnterQueue(&SQ,2);
  10. 	EnterQueue(&SQ,3);
  11. 	EnterQueue(&SQ,4);
  12. 	EnterQueue(&SQ,5);
  13. 	EnterQueue(&SQ,6);
  14. 	EnterQueue(&SQ,7);
  15. 	EnterQueue(&SQ,8);
  16. 	EnterQueue(&SQ,9);
  17. 	EnterQueue(&SQ,10);
  18. 	
  19. 	//打印队列元素 
  20. 	DispSQQueue(&SQ);
  21. 	printf("\n"); 
  22. 	printf("队列长度为：%d\n",lenghtSQQueue(&SQ)); 
  23. 	//出队
  24. 	DeleteQueue(&SQ,&e);
  25. 	printf("出队元素为：%d\n",e);
  26. 	DeleteQueue(&SQ,&e);
  27. 	printf("出队元素为：%d\n",e);
  28. 	
  29. 	//打印队列元素 
  30. 	DispSQQueue(&SQ);
  31. 	printf("\n"); 
  32. 	
  33. 	EnterQueue(&SQ,8);
  34. 	EnterQueue(&SQ,9);
  35. 	//打印队列元素 
  36. 	DispSQQueue(&SQ);
  37. 	printf("\n");
  38. 	EnterQueue(&SQ,10);
  39.  
  40. 	
  41. 	printf("队列长度为：%d\n",lenghtSQQueue(&SQ)); 
  42. 	return 1;
  43. }

测试结果如下：

 

当元素10进栈时，队满提示，并返回队列元素，在将队首元素出栈两次，返回队列元素，再将元素8，9进队，再返回队列元素，此时再将元素10进队时提示队满，返回队列长度，自此，循环队列构造完成。

最后再附上完整代码：

  1. #include <stdio.h>
  2.  
  3. #define MAXSIZE 10
  4.  
  5. typedef int ElemType;
  6.  
  7. typedef struct
  8. {
  9. 	ElemType data[MAXSIZE];//存储值 
  10. 	int front;//存储队头元素前一个单元的下标 
  11. 	int rear;//存储队尾元素的下标 
  12. }SQQueue;
  13.  
  14. /*
  15. 初始化：front=-1;rear=-1;
  17. 为了区分空和满，任意时候都预留1个单元出来
  18. x的下一个：(x+1)%MAXSIZE
  19.  
  20. 空：front==rear
  21. 满：(rear+1)%MAXSIZE==front
  23. 进队：
  24. rear=(rear+1)%MAXSIZE;
  25. data[rear]=e; 
  27. 出队：
  28. front=(front+1)%MAXSIZE;
  29. *e=data[front];
  30.  
  31. 长度：
  32. (rear-front+MAXSIZE)%MAXSIZE 
  33.  
  34. */
  35.  
  36. /*
  37. 空：q->front==NULL && q->rear==NULL 
  38. */
  39.  
  40. void InitQueue(SQQueue* SQ)
  41. {
  42. 	SQ->front = SQ->rear = -1;	
  43. 	
  44. } 
  45.  
  46. int IsEmpty(SQQueue* SQ)  //判断队列是否为空 
  47. {
  48. 	if (SQ->front == SQ->rear)
  49. 	{
  50. 		return 1;  //队空 
  51. 	}
  52. 	return 0;
  53. }
  54.  
  55. int IsFUll(SQQueue* SQ)  //判断队列是否为满 
  56. {	
  57. 	 //尾指针+1追上队头指针，标志队列已经满了
  58. 	if(((SQ->rear+1)%MAXSIZE == SQ->front)||(SQ->rear==MAXSIZE-2&&SQ->front==-1))
  59. 	{
  60. 		return 1;
  61. 	}
  62. 	return 0; //队不满 
  63. }
  64.  
  65. int EnterQueue(SQQueue* SQ,ElemType e)
  66. {
  67. 	if (IsFUll(SQ))  // (SQ->rear + 1)%MAXSIZE == SQ->front
  68. 	{
  69. 		printf("队满，不能进队。\n"); 
  70. 		return 0;
  71. 	}
  72. 	SQ->rear = (SQ->rear + 1) % MAXSIZE;
  73. 	SQ->data[SQ->rear] = e;
  74. }
  75.  
  76. int DeleteQueue(SQQueue* SQ,ElemType* e)
  77. {
  78. 	if (IsEmpty(SQ))
  79. 	{
  80. 		printf("队空，不能出队！\n");
  81. 		return 0;
  82. 	}
  83. 	SQ->front = (SQ->front+1) % MAXSIZE;
  84. 	*e = SQ->data[SQ->front];
  85. }
  86.  
  87. int lenghtSQQueue(SQQueue* SQ)
  88. {
  89. 	int len;
  90. 	len = 0;
  91. 	len = (SQ->rear-SQ->front+MAXSIZE)%MAXSIZE;	
  92. 	return len;
  93. }
  94.  
  95. void DispSQQueue(SQQueue* SQ)
  96. {
  97. 	int index;
  98. 	int i;
  99. 	
  100. 	i = 1;
  101. 	index=(SQ->front+1)%MAXSIZE;
  102. 	printf("队列元素为：");
  103. 	while(i <= lenghtSQQueue(SQ))
  104. 	{
  105. 		printf("%d ",SQ->data[index]);
  106. 		index=(index+1)%MAXSIZE; 
  107. 		
  108. 		i++;
  109. 	}
  110. }
  111.  
  112. int main()
  113. {
  114. 	SQQueue SQ;
  115. 	ElemType e;
  116. 	InitQueue(&SQ);
  117. 	
  118. 	//入队
  119. 	EnterQueue(&SQ,1);
  120. 	EnterQueue(&SQ,2);
  121. 	EnterQueue(&SQ,3);
  122. 	EnterQueue(&SQ,4);
  123. 	EnterQueue(&SQ,5);
  124. 	EnterQueue(&SQ,6);
  125. 	EnterQueue(&SQ,7);
  126. 	EnterQueue(&SQ,8);
  127. 	EnterQueue(&SQ,9);
  128. 	EnterQueue(&SQ,10);
  129. 	
  130. 	//打印队列元素 
  131. 	DispSQQueue(&SQ);
  132. 	printf("\n"); 
  133. 	printf("队列长度为：%d\n",lenghtSQQueue(&SQ)); 
  134. 	//出队
  135. 	DeleteQueue(&SQ,&e);
  136. 	printf("出队元素为：%d\n",e);
  137. 	DeleteQueue(&SQ,&e);
  138. 	printf("出队元素为：%d\n",e);
  139. 	
  140. 	//打印队列元素 
  141. 	DispSQQueue(&SQ);
  142. 	printf("\n"); 
  143. 	
  144. 	EnterQueue(&SQ,8);
  145. 	EnterQueue(&SQ,9);
  146. 	//打印队列元素 
  147. 	DispSQQueue(&SQ);
  148. 	printf("\n");
  149. 	EnterQueue(&SQ,10);
  150.  
  151. 	
  152. 	printf("队列长度为：%d\n",lenghtSQQueue(&SQ)); 
  153. 	return 1;
  154. }

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

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

  

闽ICP备14008679号