深圳幻海软件技术有限公司 欢迎您！
更多

数据结构:循环队列的实现(leetcode622.设计循环队列)

2023-03-14

head obj tail
 目录一.循环队列简单介绍二.用静态数组实现循环队列1.数组循环队列结构设计2.数组循环队列的堆区内存申请接口 3.数据出队和入队的接口实现4.其他操作接口5.数组循环队列的实现代码总览 三.静态单向循环链表实现循环队列 1.链表循环队列的结构设计2.创建静态

 

目录

一.循环队列简单介绍

二.用静态数组实现循环队列

1.数组循环队列结构设计

2.数组循环队列的堆区内存申请接口 

3.数据出队和入队的接口实现

4.其他操作接口

5.数组循环队列的实现代码总览 

三.静态单向循环链表实现循环队列 

1.链表循环队列的结构设计

2.创建静态单向循环链表的接口

3.数据的出队和入队接口

4.其他队列操作接口

5.静态链表循环队列总体代码

问题来源:622. 设计循环队列 - 力扣（Leetcode）

一.循环队列简单介绍

  • 循环队列一般是一种静态的线性数据结构,其中的数据符合先进先出的原则.
  • 循环队列的容器首地址和容器尾地址通过特定操作(比如指针链接,数组下标取余等方式)相连通,从而实现了容器空间的重复利用(在一个非循环静态队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间)

 

二.用静态数组实现循环队列

维护队列的结构体:

  1. typedef struct 
  2. {
  3.     int * arry;  //指向堆区数组的指针
  4.     int head;    //队头指针
  5.     int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)
  6.     int capacity;//静态队列的容量
  7. } MyCircularQueue;

1.数组循环队列结构设计

我们假定静态数组的容量为k(可存储k个数据)：

  • 根据队列的基本数据结构:有两个指针用于维护数组中的有效数据空间,分别为head指针和tail指针,head指针用于指向队头数据,tail用于指向队尾数据的下一个位置(即tail指针不指向有效数据)
  •  如图所示,head指针和tail指针之间就是有效数据的内存空间
  • 通过head指针和tail指针的关系来实现队列的判满(判断队列空间是否已被占满)与判空(判断队列是否为空队列)；为了达到这个目的,我们需要将静态数组的容量大小设置为k+1(即多设置一个元素空间) 
  1. 队列的判空条件: tail == head;
  2. 队列的判满条件: (tail+1)%(k+1) == head; 另外一种情形:
  • 由此我们可以先设计出队列的判满和判空接口： 
    1. bool myCircularQueueIsEmpty(MyCircularQueue* obj) //判断队列是否为空
    2. {
    3.     assert(obj);
    4.     return (obj->tail == obj->head);
    5. }
    6.  
    7. bool myCircularQueueIsFull(MyCircularQueue* obj)  //判断队列是否为满
    8. {
    9.     assert(obj);
    10.     return ((obj->tail+1)%(obj->capacity +1) == obj->head);
    11. }

2.数组循环队列的堆区内存申请接口 

  • 在堆区上创建MyCircularQueue结构体,同时为队列申请一个空间大小为(k+1)*sizeof(DataType)字节的数组： 
    1. MyCircularQueue* myCircularQueueCreate(int k)  //k个容量大小的循环队列的初始化接口
    2. {
    3.     MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    4.     //开辟维护循环队列的结构体
    5.     if(NULL == tem)
    6.     {
    7.         perror("malloc failed");
    8.         exit(-1);
    9.     }
    10.     tem->arry = NULL;
    11.     tem->capacity = k;   
    12.     //队列的数据容量为k
    13.     tem->arry = (int*)malloc((k+1)*sizeof(int));
    14.     //开辟堆区数组
    15.     if(NULL == tem->arry)
    16.     {
    17.         perror("malloc failed");
    18.         exit(-1);
    19.     }
    20.     //将head,tail下标初始化为0
    21.     tem->head = 0; 
    22.     tem->tail = 0;
    23.     return tem;
    24. }

3.数据出队和入队的接口实现

数据出队和入队的图解:

 

  •  根据图解我们可以设计出数据入队和出队的接口: 
    1. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) //数据入队接口
    2. {
    3.     assert(obj);
    4.     if(myCircularQueueIsFull(obj))
    5.     {
    6.         return false;
    7.     }
    8.     //确保队列没满
    9.     obj->arry[obj->tail]=value;
    10.     obj->tail = (obj->tail + 1)%(obj->capacity +1);
    11.     return true;
    12. }
    1. bool myCircularQueueDeQueue(MyCircularQueue* obj)    //数据出队接口
    2. {
    3.     assert(obj);
    4.     if(myCircularQueueIsEmpty(obj))
    5.     {
    6.         return false;
    7.     }
    8.     //确保队列不为空
    9.     obj->head = (obj->head +1)%(obj->capacity +1);
    10.     return true;
    11. }

4.其他操作接口

返回队头数据的接口:

  1. int myCircularQueueFront(MyCircularQueue* obj)   //返回队头数据的接口
  2. {
  3.     assert(obj);
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return -1;
  7.     }
  8.     return obj->arry[obj->head];
  9. }

 返回队尾数据的接口:

  1. int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
  2. {
  3.     assert(obj);
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return -1;
  7.     }
  8.     int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;
  9.     //注意tail如果指向数组首地址,则尾数据位于数组最后一个位置
  10.     return obj->arry[labelret];
  11. }

队列的销毁接口:

  1. void myCircularQueueFree(MyCircularQueue* obj)     //销毁队列的接口
  2. {
  3.     assert(obj);
  4.     free(obj->arry);
  5.     obj->arry = NULL;
  6.     free(obj);
  7.     obj = NULL;
  8. }

5.数组循环队列的实现代码总览 

 数组循环队列总体代码:

  1. typedef struct 
  2. {
  3.     int * arry;  //指向堆区数组的指针
  4.     int head;    //队头指针
  5.     int tail;    //队尾指针(指向队尾数据的下一个位置)(不指向有效数据)
  6.     int capacity;//静态队列容量
  7. } MyCircularQueue;
  8.  
  9.  
  10. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  11. bool myCircularQueueIsFull(MyCircularQueue* obj);
  12. //顺序编译注意:先被使用而后被定义的函数要记得进行声明
  13.  
  14. MyCircularQueue* myCircularQueueCreate(int k)          //循环队列初始化接口
  15. {
  16.     MyCircularQueue * tem = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
  17.     //开辟维护循环队列的结构体
  18.     if(NULL == tem)
  19.     {
  20.         perror("malloc failed");
  21.         exit(-1);
  22.     }
  23.     tem->arry = NULL;
  24.     tem->capacity = k;   
  25.     //队列的数据容量为k
  26.     tem->arry = (int*)malloc((k+1)*sizeof(int));
  27.     //开辟堆区数组
  28.     if(NULL == tem->arry)
  29.     {
  30.         perror("malloc failed");
  31.         exit(-1);
  32.     }
  33.     
  34.     tem->head = 0;
  35.     tem->tail = 0;
  36.     return tem;
  37. }
  38.  
  39.  
  40.  
  41. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口
  42. {
  43.     assert(obj);
  44.     if(myCircularQueueIsFull(obj))
  45.     {
  46.         return false;
  47.     }
  48.     //确保队列没满
  49.     obj->arry[obj->tail]=value;
  50.     obj->tail = (obj->tail + 1)%(obj->capacity +1);
  51.     return true;
  52. }
  53.  
  54. bool myCircularQueueDeQueue(MyCircularQueue* obj)           //数据出队接口
  55. {
  56.     assert(obj);
  57.     if(myCircularQueueIsEmpty(obj))
  58.     {
  59.         return false;
  60.     }
  61.     //确保队列不为空
  62.     obj->head = (obj->head +1)%(obj->capacity +1);
  63.     return true;
  64. }
  65.  
  66. int myCircularQueueFront(MyCircularQueue* obj)               //返回队头数据的接口
  67. {
  68.     assert(obj);
  69.     if(myCircularQueueIsEmpty(obj))
  70.     {
  71.         return -1;
  72.     }
  73.     return obj->arry[obj->head];
  74. }
  75.  
  76. int myCircularQueueRear(MyCircularQueue* obj)                 //返回队尾数据的接口     
  77. {
  78.     assert(obj);
  79.     if(myCircularQueueIsEmpty(obj))
  80.     {
  81.         return -1;
  82.     }
  83.     int labelret = ((obj->tail-1)>=0)? obj->tail-1 : obj->capacity;
  84.     //注意tail如果指向数组首地址,则尾数据位于数组最后一个位置
  85.     return obj->arry[labelret];
  86. }
  87.  
  88. bool myCircularQueueIsEmpty(MyCircularQueue* obj)              //判断队列是否为空
  89. {
  90.     assert(obj);
  91.     return (obj->tail == obj->head);
  92. }
  93.  
  94. bool myCircularQueueIsFull(MyCircularQueue* obj)               //判断队列是否为满
  95. {
  96.     assert(obj);
  97.     return ((obj->tail+1)%(obj->capacity +1) == obj->head);
  98. }
  99.  
  100. void myCircularQueueFree(MyCircularQueue* obj)                 //销毁队列的接口
  101. {
  102.     assert(obj);
  103.     free(obj->arry);
  104.     obj->arry = NULL;
  105.     free(obj);
  106.     obj = NULL;
  107. }

力扣题解测试:

三.静态单向循环链表实现循环队列 

链表节点结构体定义:

  1. typedef struct listnode
  2. {
  3.     int data;
  4.     struct listnode * next;
  5. }ListNode;

维护链表循环队列的结构体:

  1. typedef struct 
  2. {
  3.     int capacity;     //记录队列容量大小
  4.     ListNode * head;  //指向队头节点
  5.     ListNode * tail;  //指向队尾节点
  6. } MyCircularQueue;

1.链表循环队列的结构设计

静态单向循环链表的容量大小为k:

  • 与数组循环队列类似,我们同样需要开辟一个节点个数为k+1的静态循环链表
  • 链表循环队列的总体结构图示:另外一种队列判满的情形:
  1.  链表循环队列的判满条件(判断队列空间是否被占满的关系式):tail->next == head;
  2.  链表循环队列的判空条件(判断队列是否为空队列的关系式): tail == head;

链表循环队列的判满和判空的接口:

  1. bool myCircularQueueIsEmpty(MyCircularQueue* obj)    //判断队列是否为空
  2. {
  3.     assert(obj);
  4.     return(obj->head == obj->tail);
  5. }
  6.  
  7. bool myCircularQueueIsFull(MyCircularQueue* obj)     //判断队列是否为满
  8. {
  9.     assert(obj);
  10.     return (obj->tail->next == obj->head);
  11. }

2.创建静态单向循环链表的接口

实现一个接口,创建一个维护链表循环队列的结构体同时创建容量大小为k+1的静态单向循环链表:

  1. MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
  2. {
  3.     int NodeNum =k+1;                          //创建k+1个链表节点
  4.     MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
  5.     assert(object);                            //申请维护循环队列的结构体
  6.     object->capacity = k;
  7.  
  8.     ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址
  9.     while(NodeNum)
  10.     {
  11.         if(NodeNum == k+1)
  12.         {   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
  13.             assert(tem);
  14.             preNode = tem;
  15.             object->tail = object->head=tem;    //让tail和head指向同一个初始节点
  16.         }
  17.         else
  18.         {
  19.             ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
  20.             assert(tem);
  21.             preNode->next = tem;                //链接链表节点
  22.             preNode = tem;
  23.         }
  24.         NodeNum--;
  25.     }
  26.     preNode->next = object->head;               //将表尾与表头相接
  27.     return object;
  28. }

3.数据的出队和入队接口

数据出入队图解:

根据图解实现数据出入队接口:

  1. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)//数据入队接口(从队尾入队)
  2. {
  3.     assert(obj);
  4.     if(!obj || myCircularQueueIsFull(obj))  //确定队列没满
  5.     {
  6.         return false;
  7.     }           
  8.     obj->tail->data = value;                //数据入队
  9.     obj->tail = obj->tail->next;
  10.     return true;
  11. }
  1. bool myCircularQueueDeQueue(MyCircularQueue* obj)  //数据出队接口
  2. {
  3.     assert(obj);
  4.     if(!obj || myCircularQueueIsEmpty(obj))
  5.     {
  6.         return false;
  7.     }
  8.     //数据出队
  9.     obj->head = obj->head->next;
  10.     return true;
  11. }

4.其他队列操作接口

返回队头数据的接口:

  1. int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
  2. {
  3.     assert(obj);
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return -1;
  7.     }
  8.     return obj->head->data; //返回队头元素
  9. }

返回队尾数据的接口:

  1. int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
  2. {
  3.     assert(obj);
  4.     if(myCircularQueueIsEmpty(obj))
  5.     {
  6.         return -1;
  7.     }
  8.     ListNode * tem = obj->head;
  9.     while(tem->next != obj->tail)               //寻找队尾元素
  10.     {
  11.         tem=tem->next;
  12.     }
  13.     return tem->data;  //返回队尾元素
  14. }

队列销毁接口:

队列销毁过程图解:

  1. void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
  2. {
  3.     assert(obj);
  4.     //利用头指针来完成链表节点的释放
  5.     ListNode * endpoint = obj->head;           //记录一个节点释放的终点
  6.     obj->head = obj->head->next;
  7.     while(obj->head!=endpoint)
  8.     {
  9.         ListNode * tem = obj->head->next;
  10.         free(obj->head);
  11.         obj->head = tem;
  12.     }
  13.     free(endpoint);                            //释放掉终点节点
  14.     free(obj);                                 //释放掉维护环形队列的结构体
  15. }

5.静态链表循环队列总体代码

总体代码:

  1. typedef struct listnode
  2. {
  3.     int data;
  4.     struct listnode * next;
  5. }ListNode;
  6.  
  7. typedef struct 
  8. {
  9.     int capacity;
  10.     ListNode * head;
  11.     ListNode * tail;
  12.     int taildata;   //单向链表找尾复杂度为O(N),因此我们用一个变量来记录队尾数据
  13. } MyCircularQueue;
  14.  
  15.  
  16. bool myCircularQueueIsEmpty(MyCircularQueue* obj);
  17. bool myCircularQueueIsFull(MyCircularQueue* obj);
  18. //顺序编译注意:先被使用而后被定义的函数要记得进行声明
  19.  
  20.  
  21.  
  22. MyCircularQueue* myCircularQueueCreate(int k)  //循环队列初始化接口
  23. {
  24.     int NodeNum =k+1;                          //创建k+1个链表节点
  25.     MyCircularQueue* object = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
  26.     assert(object);                            //申请维护循环队列的结构体
  27.     object->capacity = k;
  28.  
  29.     ListNode * preNode = NULL;                 //用于记录前一个链接节点的地址
  30.     while(NodeNum)
  31.     {
  32.         if(NodeNum == k+1)
  33.         {   ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
  34.             assert(tem);
  35.             preNode = tem;
  36.             object->tail = object->head=tem;    //让tail和head指向同一个初始节点
  37.         }
  38.         else
  39.         {
  40.             ListNode * tem = (ListNode *)malloc(sizeof(ListNode));
  41.             assert(tem);
  42.             preNode->next = tem;                //链接链表节点
  43.             preNode = tem;
  44.         }
  45.         NodeNum--;
  46.     }
  47.     preNode->next = object->head;               //将表尾与表头相接
  48.     return object;
  49. }
  50.  
  51. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)   //数据入队接口(从队尾入队)
  52. {
  53.     assert(obj);
  54.     if(!obj || myCircularQueueIsFull(obj))  //确定队列没满
  55.     {
  56.         return false;
  57.     }           
  58.     obj->tail->data = value;                //数据入队
  59.     obj->tail = obj->tail->next;
  60.     return true;
  61. }
  62.  
  63. bool myCircularQueueDeQueue(MyCircularQueue* obj)               //数据出队接口
  64. {
  65.     assert(obj);
  66.     if(!obj || myCircularQueueIsEmpty(obj))
  67.     {
  68.         return false;
  69.     }
  70.     obj->head = obj->head->next;
  71.     return true;
  72. }
  73.  
  74. int myCircularQueueFront(MyCircularQueue* obj)  //返回队头数据的接口
  75. {
  76.     assert(obj);
  77.     if(myCircularQueueIsEmpty(obj))
  78.     {
  79.         return -1;
  80.     }
  81.     return obj->head->data;
  82. }
  83.  
  84. int myCircularQueueRear(MyCircularQueue* obj)   //返回队尾数据的接口     
  85. {
  86.     assert(obj);
  87.     if(myCircularQueueIsEmpty(obj))
  88.     {
  89.         return -1;
  90.     }
  91.     ListNode * tem = obj->head;
  92.     while(tem->next != obj->tail)               //寻找队尾元素
  93.     {
  94.         tem=tem->next;
  95.     }
  96.     return tem->data;
  97. }
  98.  
  99. bool myCircularQueueIsEmpty(MyCircularQueue* obj)                  //判断队列是否为空
  100. {
  101.     assert(obj);
  102.     return(obj->head == obj->tail);
  103. }
  104.  
  105. bool myCircularQueueIsFull(MyCircularQueue* obj)                    //判断队列是否为满
  106. {
  107.     assert(obj);
  108.     return (obj->tail->next == obj->head);
  109. }
  110.  
  111.  
  112.  
  113. void myCircularQueueFree(MyCircularQueue* obj) //销毁队列的接口
  114. {
  115.     assert(obj);
  116.     //利用头指针来完成链表节点的释放
  117.     ListNode * endpoint = obj->head;           //记录一个节点释放的终点
  118.     obj->head = obj->head->next;
  119.     while(obj->head!=endpoint)
  120.     {
  121.         ListNode * tem = obj->head->next;
  122.         free(obj->head);
  123.         obj->head = tem;
  124.     }
  125.     free(endpoint);                            //释放掉终点节点
  126.     free(obj);                                 //释放掉维护环形队列的结构体
  127. }

leetcode题解测试:

 

 

 

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览40346 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪