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

【数据结构】 循环队列的基本操作 （C语言版）_实验六 循环队列的基本操作

作者：从前慢现在也慢 | 2024-05-27 14:19:14

赞

踩

实验六 循环队列的基本操作

目录

一、顺序队列

1、顺序队列的定义：

2、顺序队列的优缺点：

二、循环队列

1、循环队列的定义：

2、循环队列的优缺点：

三、循环队列的基本操作算法（C语言）   

1、宏定义

  2、创建结构体

3、循环队列的初始化 

4、循环队列的销毁

5、循环队列的清空

6、求循环队列的长度

7、循环队列的判空

8、求队头元素

9、循环队列入队

10、循环队列出队

11、遍历队列元素

四、循环队列的基本操作完整代码（C语言）

  五、运行结果

一、顺序队列

1、顺序队列的定义：

顺序队列是由一维数组实现的队列，其中队头元素的下标为0，队尾元素的下标为n-1（n为数组大小），队列的大小在创建时确定，且在队列的生命周期内保持不变。

2、顺序队列的优缺点：

顺序队列的优点：

  1. 空间利用率高：由于数组的大小在创建时确定，因此可以预先分配足够的空间，避免了频繁的内存申请和释放操作，提高了空间利用率。
  2. 存取速度快：由于队列元素在内存中连续存储，因此可以根据下标直接访问队头元素和队尾元素，存取速度快。

顺序队列的缺点：

  1. 不适合处理动态扩展的数据：顺序队列的空间大小在创建时确定，因此无法动态扩展，对于需要处理大规模数据的情况不太适用。
  2. 容易发生假溢出：由于顺序队列的队头和队尾元素不断向后移动，当队列满时，如果继续入队操作，会导致假溢出，即无法再进行入队操作。
  3. 无法充分利用内存的连续性优势：由于顺序队列是基于数组实现的，因此无法充分利用内存的连续性优势，因为队头和队尾元素可能分散在不同的内存位置。

二、循环队列

1、循环队列的定义：

循环队列是一种线性数据结构，它将队列的元素存储在一个连续的数组中，并通过使用循环指针来管理队列的插入和删除操作。循环队列的特点在于，当队列为空时，头尾指针指向同一位置；当队列满时，头尾指针也指向同一位置。 

2、循环队列的优缺点：

循环队列的优点：

  1. 空间利用率高：循环队列使用固定大小的数组来存储元素，无需动态分配内存，因此可以充分利用存储空间。
  2. 时间复杂度稳定：在循环队列中，插入和删除操作具有固定的时间复杂度，这使得循环队列在需要频繁进行插入和删除操作的场景中表现优异。
  3. 无需额外的空间：由于循环队列使用数组实现，因此无需额外的空间来存储元素，从而降低了空间复杂度。

循环队列的缺点：

  1. 队列大小固定：循环队列的大小是固定的，因此在处理大量数据时，可能需要预先分配大量存储空间。如果实际数据量超过预分配的空间，可能会导致数据丢失或程序崩溃。
  2. 判断队列是否为空或满的判断逻辑较复杂：在循环队列中，判断队列是否为空或满的判断逻辑相对复杂。需要同时考虑头尾指针的位置和当前队列的状态。如果处理不当，可能会导致误判或错过一些特殊情况。
  3. 插入和删除操作需要移动元素：虽然循环队列在插入和删除操作时具有固定的时间复杂度，但在实际操作中，仍然需要移动元素以保持队列的连续性和循环性。如果数据量大或者数据不均匀分布，可能会影响操作效率。

三、循环队列的基本操作算法（C语言）   

1、宏定义
  1. #define OK 1
  2. #define ERROR 0
  3. #define OVERFLOW -1
  4.  
  5. #define MAXSIZE 100
  6.  
  7. typedef int QElemType;
  8. typedef int Status;
  2、创建结构体
  1. //创建结构体
  2. typedef struct {
  3.     QElemType *base;
  4.     int front;
  5.     int rear;
  6. } SqQueue;
3、循环队列的初始化 
  1. //初始化
  2. Status InitQueue(SqQueue &Q) {
  3.     //构造一个空队列
  4.     Q.base = new QElemType[MAXSIZE];
  5.     if (!Q.base) {
  6.         exit(OVERFLOW);
  7.     }
  8.     Q.front = Q.rear = 0;
  9.     return OK;
  10. }
4、循环队列的销毁
  1. //销毁队列
  2. Status DestroyQueue(SqQueue &Q) {
  3.     if (Q.base) {
  4.         delete Q.base;
  5.     }
  6.     Q.base = NULL;
  7.     Q.front = Q.rear = 0;
  8.     return OK;
  9. }
5、循环队列的清空
  1. //清空队列
  2. Status ClearQueue(SqQueue &Q) {
  3.     Q.front = Q.rear = 0;
  4.     return OK;
  5. }
6、求循环队列的长度
  1. //求长度
  2. Status QueueLength(SqQueue Q) {
  3.     return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
  4.  
  5. }
7、循环队列的判空
  1. Status QueueEmpty(SqQueue Q) {
  2.     if (Q.front == Q.rear) {
  3.         return true;
  4.     } else {
  5.         return false;
  6.     }
  7. }
8、求队头元素
  1. //求队头元素
  2. Status GetHead(SqQueue Q, QElemType &e) {
  3.     if (Q.front == Q.rear) {
  4.         return ERROR;
  5.     }
  6.     e = Q.base[Q.front];
  7.     return OK;
  8. }
9、循环队列入队
  1. //循环队列入队
  2. Status EnQueue(SqQueue &Q, QElemType e) {
  3.     if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
  4.     Q.base[Q.rear] = e;
  5.     Q.rear = (Q.rear + 1) % MAXSIZE;
  6.     return OK;
  7. }
10、循环队列出队
  1. //循环队列出队
  2. Status DeQueue(SqQueue &Q, QElemType &e) {
  3.     if (Q.front == Q.rear) {
  4.         return ERROR;
  5.     }
  6.     e = Q.base[Q.front];
  7.     Q.front = (Q.front + 1) % MAXSIZE;
  8.     return OK;
  9. }
11、遍历队列元素
  1. //遍历队列
  2. void DisplayQueue(SqQueue Q) {
  3.     int i = Q.front;
  4.     printf("队列元素为： ");
  5.     while (Q.front != Q.rear && (i + MAXSIZE) % MAXSIZE != Q.rear) {
  6.         printf("%d ", Q.base[i]);
  7.         i++;
  8.     }
  9. }
四、循环队列的基本操作完整代码（C语言）
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define OK 1
  5. #define ERROR 0
  6. #define OVERFLOW -1
  7.  
  8. #define MAXSIZE 100
  9.  
  10. typedef int QElemType;
  11. typedef int Status;
  12.  
  13. //创建结构体
  14. typedef struct {
  15.     QElemType *base;
  16.     int front;
  17.     int rear;
  18. } SqQueue;
  19.  
  20. //初始化
  21. Status InitQueue(SqQueue &Q) {
  22.     //构造一个空队列
  23.     Q.base = new QElemType[MAXSIZE];
  24.     if (!Q.base) {
  25.         exit(OVERFLOW);
  26.     }
  27.     Q.front = Q.rear = 0;
  28.     return OK;
  29. }
  30.  
  31. //销毁队列
  32. Status DestroyQueue(SqQueue &Q) {
  33.     if (Q.base) {
  34.         delete Q.base;
  35.     }
  36.     Q.base = NULL;
  37.     Q.front = Q.rear = 0;
  38.     return OK;
  39. }
  40.  
  41. //清空队列
  42. Status ClearQueue(SqQueue &Q) {
  43.     Q.front = Q.rear = 0;
  44.     return OK;
  45. }
  46.  
  47. //求长度
  48. Status QueueLength(SqQueue Q) {
  49.     return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
  50.  
  51. }
  52.  
  53. //判空
  54. Status QueueEmpty(SqQueue Q) {
  55.     if (Q.front == Q.rear) {
  56.         return true;
  57.     } else {
  58.         return false;
  59.     }
  60. }
  61.  
  62. //求队头元素
  63. Status GetHead(SqQueue Q, QElemType &e) {
  64.     if (Q.front == Q.rear) {
  65.         return ERROR;
  66.     }
  67.     e = Q.base[Q.front];
  68.     return OK;
  69. }
  70.  
  71. //循环队列入队
  72. Status EnQueue(SqQueue &Q, QElemType e) {
  73.     if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
  74.     Q.base[Q.rear] = e;
  75.     Q.rear = (Q.rear + 1) % MAXSIZE;
  76.     return OK;
  77. }
  78.  
  79. //循环队列出队
  80. Status DeQueue(SqQueue &Q, QElemType &e) {
  81.     if (Q.front == Q.rear) {
  82.         return ERROR;
  83.     }
  84.     e = Q.base[Q.front];
  85.     Q.front = (Q.front + 1) % MAXSIZE;
  86.     return OK;
  87. }
  88.  
  89. //遍历队列
  90. void DisplayQueue(SqQueue Q) {
  91.     int i = Q.front;
  92.     printf("队列元素为： ");
  93.     while (Q.front != Q.rear && (i + MAXSIZE) % MAXSIZE != Q.rear) {
  94.         printf("%d ", Q.base[i]);
  95.         i++;
  96.     }
  97. }
  98.  
  99. //功能菜单列表
  100. void show_help() {
  101.     printf("******* 功能菜单列表 *******\n");
  102.     printf("1----入队------------------\n");
  103.     printf("2----求循环队列长度----------\n");
  104.     printf("3----出队------------------\n");
  105.     printf("4----取队头元素-------------\n");
  106.     printf("5----清空循环队列-----------\n");
  107.     printf("6----销毁循环队列-----------\n");
  108.     printf("7----判断循环队列是否为空-----\n");
  109.     printf("8----批量插入元素------------\n");
  110.     printf("9----显示队列元素------------\n");
  111.     printf("10----退出------------------\n\n");
  112. }
  113.  
  114. int main() {
  115.     SqQueue sq;
  116.  
  117.     //初始化
  118.     Status rInitStack = InitQueue(sq);
  119.     if (rInitStack == OK) {
  120.         printf("循环队列初始化成功！\n");
  121.     } else {
  122.         printf("循环队列初始化失败！\n");
  123.     }
  124.  
  125.  
  126.     while (1) {
  127.  
  128.         //功能菜单列表
  129.         show_help();
  130.  
  131.         int flag;
  132.         printf("请输入所需的功能编号：\n");
  133.         scanf("%d", &flag);
  134.  
  135.         switch (flag) {
  136.             case 1: {//入队
  137.                 Status EnQueueindex;
  138.                 printf("请输入插入元素(请在英文状态下输入例如:1): \n");
  139.                 scanf("%d", &EnQueueindex);
  140.                 Status rEnQueue = EnQueue(sq, EnQueueindex);
  141.                 if (rEnQueue == OK) {
  142.                     printf("向循环队列入队%d成功！\n", EnQueueindex);
  143.                 } else {
  144.                     printf("向循环队列入队失败！\n");
  145.                 }
  146.             }
  147.                 break;
  148.             case 2: {//求循环队列的长度
  149.                 int length = QueueLength(sq);
  150.                 printf("循环队列的长度为:%d。 \n\n", length);
  151.             }
  152.                 break;
  153.             case 3: {//出队
  154.                 Status DeQueueindex;
  155.                 Status rDeQueue = DeQueue(sq, DeQueueindex);
  156.                 if (rDeQueue == OK) {
  157.                     printf("向循环队列出队%d成功！\n", DeQueueindex);
  158.                 } else {
  159.                     printf("向循环队列出队失败！\n");
  160.                 }
  161.             }
  162.                 break;
  163.             case 4: {//求队头元素
  164.                 Status topData;
  165.                 Status rGetHead = GetHead(sq, topData);
  166.                 if (rGetHead == OK) {
  167.                     printf("向循环队列获取队头元素：%d\n", topData);
  168.                 } else {
  169.                     printf("向循环队列获取队头元素失败！\n");
  170.                 }
  171.             }
  172.                 break;
  173.             case 5: { //清空
  174.                 Status rClearStack = ClearQueue(sq);
  175.                 if (rClearStack == OK) {
  176.                     printf("循环队列清空成功！\n");
  177.                 } else {
  178.                     printf("循环队列清空失败！\n");
  179.                 }
  180.             }
  181.                 break;
  182.             case 6: {//销毁
  183.                 Status rDestroyStack = DestroyQueue(sq);
  184.                 if (rDestroyStack == OK) {
  185.                     printf("循环队列销毁成功！\n");
  186.                 } else {
  187.                     printf("循环队列销毁失败！\n");
  188.                 }
  189.             }
  190.                 break;
  191.             case 7: {///判空
  192.                 Status ClearStatus = QueueEmpty(sq);
  193.                 if (ClearStatus == true) {
  194.                     printf("循环队列为空！\n\n");
  195.                 } else {
  196.                     printf("循环队列不为空！\n\n");
  197.                 }
  198.             }
  199.                 break;
  200.             case 8: {//批量插入
  201.                 int on;
  202.                 printf("请输入想要插入的元素个数：\n");
  203.                 scanf("%d", &on);
  204.                 QElemType array[on];
  205.                 for (int i = 1; i <= on; i++) {
  206.                     printf("向循环队列第%d个位置插入元素为:", i);
  207.                     scanf("%d", &array[i]);
  208.                 }
  209.  
  210.                 for (int i = 1; i <= on; i++) {
  211.                     Status InsertStatus = EnQueue(sq, array[i]);
  212.                     if (InsertStatus == OK) {
  213.                         printf("向循环队列第%d个位置插入元素%d成功！\n", i, array[i]);
  214.                     } else {
  215.                         printf("向循环队列第%d个位置插入元素%d失败！\n", i, array[i]);
  216.                     }
  217.                 }
  218.             }
  219.                 break;
  220.             case 9: {//输出链表元素
  221.                 DisplayQueue(sq);
  222.                 printf("\n");
  223.             }
  224.                 break;
  225.             case 10: {//退出程序
  226.                 return 0;
  227.             }
  228.                 break;
  229.             default: {
  230.                 printf("输入错误，无此功能，请检查输入:\n\n");
  231.             }
  232.         }
  233.     }
  234.  
  235.     return 1;
  236. }

  五、运行结果

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

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

  

闽ICP备14008679号