当前位置:   article > 正文

【数据结构】循环队列(数组实现)_用一个数组表示循环队列

用一个数组表示循环队列

目录

一、循环队列定义

怎么使一个数组在逻辑上呈“环状”呢?

 二、循环队列与顺序队列的差异

1、存储方式:

2、操作方式:

3、空间利用率:

4、循环队列判断队空的方式:

5、循环队列判断队满的方式

完整测试代码及注释: 

总结:


一、循环队列定义

将顺序存储队列的元素的一维数组首尾相接,形成一个环状,如下图所示,这种形式表示的队列称为循环队列。循环队列仍然是顺序队列结构,只是逻辑上和前面的顺序队列有所不同。

  1. #define MAXLEN 6 // 定义环形队列的最大长度为 6
  2. typedef int DataType; // 定义数据类型为整型
  3. typedef struct CircularQueue // 定义环形队列的结构体
  4. {
  5. DataType a[MAXLEN]; // 定义存储数据的数组
  6. int front, rear; // 定义队头和队尾指针
  7. int size; // 定义队列元素个数
  8. } CQueue;
  9. void InitCQueue(CQueue* q) // 初始化环形队列
  10. {
  11. q->front = q->rear = 0; // 队头和队尾指针都指向队列的开始位置
  12. q->size = 0; // 队列元素个数为 0,即初始为空队列
  13. }

怎么使一个数组在逻辑上呈“环状”呢?

数据结构中,可以使用一个 front 指针和一个 rear 指针来表示环状队列的队头和队尾位置,当 rear 指针移动到数组的最后一个位置时,如果再有元素需要入队,那么应该将 rear 指针指向数组的第一个位置。同样地,当 front 指针移动到数组的最后一个位置时,如果还有元素需要出队,那么应该将 front 指针指向数组的第一个位置。

具体实现方法如下:

  1. 初始化:定义一个数组和两个指针 front 和 rear,初始化时,将 front 指针和 rear 指针都指向数组的第一个位置。

  2. 入队:如果队列未满,则将元素插入 rear 指向的位置,然后将 rear 指针后移一位。当 rear 指针移动到数组的最后一个位置时,若队列未满,则将 rear 指针指向数组的第一个位置。

  3. 出队:如果队列非空,则将队头元素取出,然后将 front 指针后移一位。当 front 指针移动到数组的最后一个位置时,只要队列非空,就将 front 指针指向数组的第一个位置。

假设队列开辟的数组单元数为MAXSIZE,它的数组下标在0~MAXSIZE-1之间,若使队头或队尾增1,且使front和rear指针对应的数组下标保持在数组范围内,可以利用取模运算实现。


例如,在下图所示的循环队列示意图最大空间为MAXSIZE=8,数组下标为0~7之间。

非空队时如图(2)中队头指针front指向队列中队头元素的前一个位置队尾指针rear 指向队列的队尾元素位置。

  •         入队时的队尾指针加1操作修改为: rear=(rear+1)%MAXSIZE;
  •         出队时的队头指针加1操作修改为:front=(front+1)%MAXSIZE;

入队代码实现: 

  1. void CQueuePush(CQueue* q, DataType x) // 元素入队
  2. {
  3. assert(q); // 判断 q 是否为空
  4. if (!CQueueFull(q)) // 如果队列未满
  5. {
  6. q->rear = (q->rear + 1) % MAXLEN; // 队尾指针后移一位
  7. q->a[q->rear] = x; // 在队尾处添加元素
  8. q->size++; // 队列元素个数加 1
  9. }
  10. else // 队列已满,无法添加数据
  11. {
  12. printf("队列已满,无法添加数据!\n");
  13. exit(-1);
  14. }
  15. }

 出队代码实现: 

  1. void CQueuePop(CQueue* q) // 元素出队
  2. {
  3. assert(q); // 判断 q 是否为空
  4. if (!CQueueEmpty(q)) // 如果队列非空
  5. {
  6. q->front = (q->front + 1) % MAXLEN; // 队头指针后移一位
  7. q->size--; // 队列元素个数减 1
  8. }
  9. else // 队列已空,无法删除数据
  10. {
  11. printf("队列已空,无法删除数据!\n");
  12. exit(-1);
  13. }
  14. }


 二、循环队列与顺序队列的差异

  • 1、存储方式:

    • 顺序队列:使用数组作为底层数据结构,按照顺序存储元素。
    • 循环队列:仍然使用数组作为底层数据结构,但是通过循环利用数组的空间,实现循环存储。
  • 2、操作方式:

    • 顺序队列:使用两个指针front和rear分别表示队头和队尾,元素入队时rear指针后移,元素出队时front指针后移。
    • 循环队列:同样使用两个指针front和rear表示队头和队尾,但是在数据满或空的状态下,指针继续向后移动的时候保持循环关系。
      • 入队时队尾指针+1:rear=(rear+1)%MAXSIZE;
      • 出队时队头指针+1:front=(front+1)%MAXSIZE;
  • 3、空间利用率:

    • 顺序队列:存储元素的空间是连续的,当队列未满但是数组的末尾已经被利用时,无法继续插入元素。
    • 循环队列:通过循环利用数组空间,解决了顺序队列存储空间的浪费问题,可以实现更高的空间利用率。

4、循环队列判断队空的方式:

图(1)中队头与队尾指针指向同一位置时为空队,判断方法与顺序队列一致。

 代码实现:

  1. int CQueueEmpty(CQueue* q) // 判断队列是否为空
  2. {
  3. assert(q); // 判断 q 是否为空
  4. if (q->front == q->rear) // 通过队头和队尾指针是否相等,判断队列是否为空
  5. {
  6. return 1; // 队列为空
  7. }
  8. return 0; // 队列非空
  9. }

5、循环队列判断队满的方式

由 图(3) 可见,循环队列解决了顺序队列中“假溢出”的现象,充分利用了固定长度的队列中的空间。我们知道,在长度不可增长的顺序队列中,判断队列是否队满的条件是rear==MAXLEN。那么在循环队列中,我们判断队满的方式则为:(rear+1)%MAXLEN==front;  


 

代码实现:

  1. int CQueueFull(CQueue* q) // 判断队列是否为满
  2. {
  3. assert(q); // 判断 q 是否为空
  4. if ((q->rear + 1) % MAXLEN == q->front) // 通过队尾和队头指针是否相邻,判断队列是否为满
  5. {
  6. return 1; // 队列为满
  7. }
  8. return 0; // 队列未满
  9. }

我们理解完顺序队列与循环队列的差异后,在固定长度代码的基础上对front、rear指针的移动判满操作进行修改即可得到循环队列的代码。


完整测试代码及注释: 

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #include<assert.h>
  5. #define MAXLEN 6 // 定义环形队列的最大长度为 6
  6. typedef int DataType; // 定义数据类型为整型
  7. typedef struct CircularQueue // 定义环形队列的结构体
  8. {
  9. DataType a[MAXLEN]; // 定义存储数据的数组
  10. int front, rear; // 定义队头和队尾指针
  11. int size; // 定义队列元素个数
  12. } CQueue;
  13. void InitCQueue(CQueue* q) // 初始化环形队列
  14. {
  15. q->front = q->rear = 0; // 队头和队尾指针都指向队列的开始位置
  16. q->size = 0; // 队列元素个数为 0,即初始为空队列
  17. }
  18. int CQueueFull(CQueue* q) // 判断队列是否为满
  19. {
  20. assert(q); // 判断 q 是否为空
  21. if ((q->rear + 1) % MAXLEN == q->front) // 通过队尾和队头指针是否相邻,判断队列是否为满
  22. {
  23. return 1; // 队列为满
  24. }
  25. return 0; // 队列未满
  26. }
  27. int CQueueEmpty(CQueue* q) // 判断队列是否为空
  28. {
  29. assert(q); // 判断 q 是否为空
  30. if (q->front == q->rear) // 通过队头和队尾指针是否相等,判断队列是否为空
  31. {
  32. return 1; // 队列为空
  33. }
  34. return 0; // 队列非空
  35. }
  36. void CQueuePush(CQueue* q, DataType x) // 元素入队
  37. {
  38. assert(q); // 判断 q 是否为空
  39. if (!CQueueFull(q)) // 如果队列未满
  40. {
  41. q->rear = (q->rear + 1) % MAXLEN; // 队尾指针后移一位
  42. q->a[q->rear] = x; // 在队尾处添加元素
  43. q->size++; // 队列元素个数加 1
  44. }
  45. else // 队列已满,无法添加数据
  46. {
  47. printf("队列已满,无法添加数据!\n");
  48. exit(-1);
  49. }
  50. }
  51. void CQueuePop(CQueue* q) // 元素出队
  52. {
  53. assert(q); // 判断 q 是否为空
  54. if (!CQueueEmpty(q)) // 如果队列非空
  55. {
  56. q->front = (q->front + 1) % MAXLEN; // 队头指针后移一位
  57. q->size--; // 队列元素个数减 1
  58. }
  59. else // 队列已空,无法删除数据
  60. {
  61. printf("队列已空,无法删除数据!\n");
  62. exit(-1);
  63. }
  64. }
  65. int CQueueTop(CQueue* q) // 获取队首元素
  66. {
  67. if (!CQueueEmpty(q)) // 如果队列非空
  68. {
  69. return q->a[q->front + 1]; // 返回队头下一个位置的元素
  70. }
  71. else // 队列已空,无法获取队首数据
  72. {
  73. printf("队列已空,无法获取队首数据!\n");
  74. exit(-1);
  75. }
  76. }
  77. int CQueueTail(CQueue* q) // 获取队尾元素
  78. {
  79. if (!CQueueEmpty(q)) // 如果队列非空
  80. {
  81. return q->a[q->rear]; // 返回队尾位置的元素
  82. }
  83. else // 队列已空,无法获取队尾数据
  84. {
  85. printf("队列已空,无法获取队尾数据!\n");
  86. exit(-1);
  87. }
  88. }
  89. int main()
  90. {
  91. CQueue q;
  92. InitCQueue(&q);
  93. CQueuePush(&q, 1);
  94. CQueuePush(&q, 2);
  95. CQueuePush(&q, 3);
  96. CQueuePush(&q, 4);
  97. CQueuePush(&q, 5);
  98. CQueuePop(&q);
  99. CQueuePop(&q);
  100. CQueuePop(&q);
  101. CQueuePop(&q);
  102. //CQueuePop(&q);
  103. int x;
  104. x = CQueueTop(&q);
  105. printf("%d\n", x);
  106. x = CQueueTail(&q);
  107. printf("%d\n", x);
  108. return 0;
  109. }

总结:

循环队列通过环形数组的设计,充分利用了存储空间,并实现了高效的元素入队和出队操作。在使用循环队列时,需要特别注意队列为空和队列满的判断,避免出现错误。

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

闽ICP备14008679号