目录

【Leetcode622】设计循环队列

A.链接

B.题目再现

 C.解法

【Leetcode622】设计循环队列

A.链接

设计循环队列

B.题目再现

 C.解法

其实这题用数组或是链表都能解决    
    
    
，但是如果是用链表的话   


     


     


，那么队列为空的条件和队列满了的条件是一样的



 




 




 ，都为 front==rear   

   

   
，这样就无法判断    

     

     

，加个哨兵位的头节点可以解决这个问题




  




  




 ，但是后面接口的实现又会很麻烦  


  


  
，所以这题还是推荐用数组实现  
    
    
。

创建数组时     
     
     
，我们多开1个空间




   




   




 ，也就是开 k+1 个空间；

具体来说：

刚开始队列为空
 



 



 
，所以 front==rear==0；

1.插入数据时               ，在下标为 rear 的位置插入 




    




    




 ，然后rear++,为了防止下次插入数据时越界












，rear还要模上 k+1 ；

当rear+1==front即队列满了               ，就不能插入  



     



     



 ，返回false












，但是这里不能简单地判断 rear+1==front    
    
    
，因为有几种特殊的情况需要注意:

2.删除数据时   


     


     


，要先判断队列是否为空



 




 




 ，若为空则返回false；

若不为空   

   

   
，只需让front++    

     

     

，注意这了还是要让front 模上k+1




  




  




 ，防止加着加着就越界了

     


     


     。

3.获取队头数据很简单  


  


  
，只需要在此之前判断队列是否为空     
     
     
，为空则返回-1；

不为空则返回 front；

4.获取队尾数据时




   




   




 ，在此之前同样需要判空
 



 



 
，若为空               ，则返回-1；

若不为空 




    




    




 ，因为 rear 始终表示的是下一个位置












，所以返回 rear -1               ，但是如果 rear 的值是0的话  



     



     



 ，rear-1==-1












，访问就越界了    
    
    
，这个特殊的情况需要注意   


     


     


，或者不单独判断这个特殊情况



 




 




 ，直接先让rear-1   

   

   
，再加上k+1    

     

     

，然后模上k+1




  




  




 ，返回其结果  


  


  
，这样即使rear是0     
     
     
，也不会造成越界访问 




 




 



。

5.判空很简单




   




   




 ，只需判断 rear 是否等于 front 即可  

   

   

。

typedef struct { int *arr; int front; int rear; int k; } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj) { //不能简单地判断rear+1==front即为满
 



 



 
，要考虑特殊情况 return ((obj->rear+1)%(obj->k+1))==(obj->front); } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { if(obj->front==obj->rear) return true; else return false; } MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); if(obj==NULL) return NULL; obj->front=obj->rear=0; obj->k=k; //这里记录k的值               ，后面的接口需要用到 obj->arr=(int *)malloc(sizeof(int)*(k+1)); //开 k+1 个空间 if(obj->arr==NULL) return NULL; return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) //队列为满则返回false return false; obj->arr[obj->rear++]=value; obj->rear%=(obj->k+1); //防止 rear 加着加着就越界了 return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) //队列为空则返回false return false; obj->front++; obj->front%=(obj->k+1); //防止 front 加着加着就越界了 return true; } int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) //队列为空则返回-1 return -1; return obj->arr[obj->front]; } int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) return -1; //rear表示的是下一个位置 




    




    




 ，所以队尾数据的下标时rear-1












，但要考虑rear==0 这一特殊情况 return obj->arr[(obj->rear-1+obj->k+1)%(obj->k+1)]; } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); //先销毁创建的数组 free(obj); }

🐲👻这循环队列的讲解就到这里了               ，若有错误或是建议欢迎小伙伴们指出

     

     

    。🐯🤖

🥰🤩希望小伙伴们可以多多支持博主哦  




  




  


。😍😃

😁😄谢谢你的阅读  


  


  


。😼😸