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

循环队列（C语言）

作者：我家小花儿 | 2024-07-08 13:14:27

赞

踩

循环队列

1.定义：

        循环队列（Circular Queue），也被称为环形队列或循环缓冲区，是一种队列数据结构，它具有固定大小的缓冲区，允许在队列的前面和后面插入和删除元素。与普通队列不同，循环队列可以避免浪费存储空间的问题，因为当队列的尾部元素达到缓冲区的末尾时，它可以"循环"到缓冲区的开头。

2.主要特点：

  1. 固定大小：循环队列有一个预定义的大小，一旦分配了这个大小，就不能动态调整。

  2. 循环性质：当队列的尾部指针（rear）到达缓冲区的末尾时，下一个元素将被插入到缓冲区的开头。这种循环性质使得队列的数据结构紧凑，不会浪费存储空间。

  3. 前后指针：循环队列通常有两个指针，一个指向队列的头部（front），另一个指向队列的尾部（rear）。

  4. 满队列判定：为了区分队列是空的还是满的，可以采用不同的方法。一种常见的方法是在插入元素时检查(rear+1)%n == front，其中n是队列的大小。如果这个条件成立，队列被认为是满的。

  5. 避免数据搬移：与普通队列相比，循环队列的插入和删除操作更加高效，因为元素不需要搬移。普通队列在出队操作后，需要将后续元素向前搬移一个位置，而循环队列不需要这样做。

  6. 应用：循环队列常常用于需要固定大小缓冲区的场景。

3.示例图：

4.主要操作

  • 入队：在队尾插入元素，并将rear指针向后移动。

  • 出队：从队头删除元素，并将front指针向后移动。

  • 判满：检查队列是否已满。

  • 判空：检查队列是否为空。

  • 查看队首元素：返回 front 指针所指向的元素。
  • 查看队列长度：返回 rear 指针与 front 指针之间的元素个数。

5.循环队列的实现

5.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;

5.2初始化

接收一个指向循环队列的指针，函数返回0，表示初始化成功。

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

运行图：

5.3入队：需要判断队列是否满了，若不满，则可入队

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

首先检查队列是否已满。如果队列已满，则打印一条消息"队列已满！100001"，并返回一个错误代码100001。 如果队列没有满，那么函数会计算rear指针的新位置。在循环队列中，当rear指针到达数组的末尾时，它会循环回到数组的开头。函数返回0，表示操作成功。

5.4出队

首先检查队列是否为空。如果队列为空，则打印一条消息"队列为空！100002"，并返回一个错误代码100002。

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

出队从队首出队。

5.5队满

队列的rear指针加1后对MAXSIZE取模的结果等于front指针，那么队列已满，函数返回1；否则，队列未满，函数返回0。

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

5.6队空：队列的front指针和rear指针相等，那么队列为空，函数返回1；否则，队列不为空，函数返回0。

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

5.7求队列长度：队列的长度可以通过计算rear指针和front指针之间的距离来得到。

  1. //队列长度
  2. int getLength(CirclesQueue *Q);
  3. //队列长度
  4. int getLength(CirclesQueue *Q) {
  5.     return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
  6. }

5.8输出队列：检查队列是否为空。

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

5.9：取队首

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

5.10帮助：

  1.         case 9:
  2.                 printf("这个程序由万佳劲编写，有初始化队列，入队，出队，判断为空，是否满，队首，队列长度，输出队列功能，如有问题，请及时联系作者\n");
  3.                 break;

 6.完整demo

6.1CirclesQueue.h

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

6.2 CirclesQueue.c

  1. /*
  2. 	CirclesQueue.c
  3. */
  4.  
  5. /*循环队列初始化*/
  6. int init(CirclesQueue *Q)
  7. {
  8.     Q->front = Q->rear = 0;
  9.     return 0;
  10. }
  11.  
  12.  
  13. /*入队*/
  14. int enqueue(CirclesQueue *Q, DataType x)
  15. {
  16.     if(isfull(Q))
  17.     {
  18.         printf("队列已满！100001\n");
  19.         return 100001;
  20.     }
  21.  
  22.     Q->rear = (Q->rear+1) % MAXSIZE;
  23.     Q->data[Q->rear] = x;
  24.     return 0;
  25. }
  26.  
  27. /*队满？*/
  28. int isfull(CirclesQueue *Q)
  29. {
  30.     return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
  31. }
  32.  
  33.  
  34. /*出队*/
  35. int dequeue(CirclesQueue *Q, DataType *x)
  36. {
  37.     if(isempty(Q))
  38.     {
  39.         printf("队列为空！100002\n");
  40.         return 100002;
  41.     }
  42.     Q->front = (Q->front+1) % MAXSIZE;
  43.     *x = Q->data[Q->front];
  44.     return 0;
  45. }
  46.  
  47. /*队空*/
  48. int isempty(CirclesQueue *Q)
  49. {
  50.     return (Q->front == Q->rear) ? 1 : 0;
  51. }
  52.  
  53. //队列长度
  54. int getLength(CirclesQueue *Q) {
  55.     return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
  56. }
  57.  
  58. // 输出队列内容
  59. void printQueue(CirclesQueue *Q) {
  60.     int i;
  61.     if (isempty(Q)) {
  62.         printf("Queue is empty.\n");
  63.         return;
  64.     }
  65.     i = (Q -> front) %MAXSIZE;
  66.     do{
  67.         printf(" %d",Q -> data[(i + 1 % MAXSIZE)]);
  68.         i = (i+1) %MAXSIZE;
  69.     }while(i != Q -> rear);
  70. }
  71.  
  72. // 获取队首元素
  73. DataType getFront(CirclesQueue* Q) {
  74.     int i;
  75.     i = (Q -> front) %MAXSIZE;
  76.     return Q -> data[(i + 1 % MAXSIZE)];
  77. }

welcome

  1. char welcome[] = "\n\
  2.            \t_ooOoo_\n"
  3.                  "                             o8888888o\n"
  4.                  "                             88\" . \"88\n"
  5.                  "                             (| -_- |)\n"
  6.                  "                             O\\  =  /O\n"
  7.                  "                          ____/`---'\\____\n"
  8.                  "                        .'  \\\\|     |//  `.\n"
  9.                  "                       /  \\\\|||  :  |||//  \\ \n"
  10.                  "                      /  _||||| -:- |||||-  \\ \n"
  11.                  "                      |   | \\\\\\  -  /// |   |\n"
  12.                  "                      | \\_|  ''\\---/''  |   |\n"
  13.                  "                      \\  .-\\__  `-`  ___/-. /\n"
  14.                  "                    ___`. .'  /--.--\\  `. . __\n"
  15.                  "                 .\"\" '<  `.___\\_<|>_/___.'  >'\"\".\n"
  16.                  "                | | :  `- \\`.;`\\ _ /`;.`/ - ` : | |\n"
  17.                  "                \\  \\ `-.   \\_ __\\ /__ _/   .-` /  /\n"
  18.                  "         ======`-.____`-.___\\_____/___.-`____.-'======\n"
  19.                  "                             `=---='\n\n";

main.c

  1. int main(int argc, char* argv[]) {
  2.     CirclesQueue Q;
  3.     DataType x;
  4.     int cmd;
  5.     char yn;
  6. do {
  7.         printf("-----------循环队列演示-----------\n");
  8.         printf(" 1. 初始化\n");
  9.         printf(" 2. 入队\n");
  10.         printf(" 3. 出队\n");
  11.         printf(" 4. 队空？\n");
  12.         printf(" 5. 队满\n");
  13.         printf(" 6.队列长度 \n");
  14.         printf(" 7.输出队列 \n");
  15.         printf(" 8.取队首 \n");
  16.         printf(" 9.帮助 \n");
  17.         printf(" 0. 退出\n");
  18.         printf(" 请选择（0~6）：");
  19.         scanf("%d", &cmd);
  20.         switch (cmd) {
  21.             case 1:
  22.                 init(&Q);
  23.                 printf("队列已初始化！\n");
  24.                 break;
  25.             case 2:
  26.                 printf("请输入要入队的元素x=");
  27.                 scanf("%d", &x);
  28.                 if (!enqueue(&Q, x)) {
  29.                     printf("元素x=%d已入队\n", x);
  30.                 }
  31.                 break;
  32.             case 3:
  33.                 printf("确定要出队（出队会将删除对首元素, y or n, n）？");
  34. //                flushall();
  35.                 scanf("%c", &yn);
  36.  
  37.                 if (yn == 'y' || yn == 'Y') {
  38.                     if (!dequeue(&Q, &x)) {
  39.                         printf("队首元素【%d】已出队！\n", x);
  40.                     }
  41.                 }
  42.                 break;
  43.             case 4:
  44.                 if(isempty(&Q)) printf("队列为空！\n");
  45.                 else printf("队列不为空！\n");
  46.                 break;
  47.             case 5:
  48.                 if(isfull(&Q)) printf("队列已满！\n");
  49.                 else printf("队列还没有满！\n");
  50.                 break;
  51.             case 6:
  52.                 printf("队列的长度：%d\n",getLength(&Q));
  53.                 break;
  54.             case 7:
  55.                 printf("输出队列：%d\n");
  56.                 printQueue(&Q);
  57.                 printf("\n");
  58.                 break;
  59.             case 8:
  60.                 printf("取队首：%d\n",getFront(&Q));
  61.                 break;
  62.             case 9:
  63.                 printf("这个程序由万佳劲编写，有初始化队列，入队，出队，判断为空，是否满，队首，队列长度，输出队列功能，如有问题，请及时联系作者\n");
  64.                 break;
  65.  
  66.         }
  67.  
  68.     } while (cmd != 0);
  69.  
  70.  
  71.     return 0;
  72. }

7.总结

实现循环队列时，需要小心处理rear和front指针的循环移动，确保在操作时正确地维护它们的位置。

总之，循环队列是一种非常有用的数据结构，适用于需要固定大小缓冲区的情况，可以有效地管理元素的插入和删除，而不浪费存储空间。感谢季老师的教学与指导，才有了最终的一篇拙作。

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

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

  

闽ICP备14008679号