【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 即可。
1. typedef struct { 2. int *arr; 3. int front; 4. int rear; 5. int k; 6. } MyCircularQueue; 7. 8. bool myCircularQueueIsFull(MyCircularQueue* obj) 9. { 10. //不能简单地判断rear+1==front即为满，要考虑特殊情况 11. return ((obj->rear+1)%(obj->k+1))==(obj->front); 12. } 13. 14. bool myCircularQueueIsEmpty(MyCircularQueue* obj) 15. { 16. if(obj->front==obj->rear) 17. return true; 18. else 19. return false; 20. } 21. MyCircularQueue* myCircularQueueCreate(int k) 22. { 23. MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); 24. if(obj==NULL) 25. return NULL; 26. obj->front=obj->rear=0; 27. obj->k=k; //这里记录k的值，后面的接口需要用到 28. obj->arr=(int *)malloc(sizeof(int)*(k+1)); //开 k+1 个空间 29. if(obj->arr==NULL) 30. return NULL; 31. return obj; 32. } 33. 34. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 35. { 36. if(myCircularQueueIsFull(obj)) //队列为满则返回false 37. return false; 38. obj->arr[obj->rear++]=value; 39. obj->rear%=(obj->k+1); //防止 rear 加着加着就越界了 40. return true; 41. } 42. 43. bool myCircularQueueDeQueue(MyCircularQueue* obj) 44. { 45. if(myCircularQueueIsEmpty(obj)) //队列为空则返回false 46. return false; 47. obj->front++; 48. obj->front%=(obj->k+1); //防止 front 加着加着就越界了 49. return true; 50. } 51. 52. int myCircularQueueFront(MyCircularQueue* obj) 53. { 54. if(myCircularQueueIsEmpty(obj)) //队列为空则返回-1 55. return -1; 56. return obj->arr[obj->front]; 57. } 58. 59. int myCircularQueueRear(MyCircularQueue* obj) 60. { 61. if(myCircularQueueIsEmpty(obj)) 62. return -1; 63. //rear表示的是下一个位置，所以队尾数据的下标时rear-1，但要考虑rear==0 这一特殊情况 64. return obj->arr[(obj->rear-1+obj->k+1)%(obj->k+1)]; 65. } 66. 67. void myCircularQueueFree(MyCircularQueue* obj) 68. { 69. free(obj->arr); //先销毁创建的数组 70. free(obj); 71. }
🐲👻这循环队列的讲解就到这里了，若有错误或是建议欢迎小伙伴们指出。🐯🤖
🥰🤩希望小伙伴们可以多多支持博主哦。😍😃
😁😄谢谢你的阅读。😼😸
