【数据结构初阶第十二节】设计循环队列

云边有个稻草人-CSDN博客

必须有为成功付出代价的决心，然后想办法付出这个代价。

还有最后一道关于队列的习题，这题有点难，准备好迎接挑战吧！ 

目录

1.【题目】

2.实现循环队列推荐用数组，Why?

3.Q1：如何来判断队列是满的？

4.上代码！

5.【注意】

---

这题得多画图理解，不能空想，而且要结合我写代码中穿插的注释，这样就会好理解点

1.【题目】

2.实现循环队列推荐用数组，Why?

链表：如果像我们实现队列一样使用链表，定义两个指针，phead为头删除数据，ptail为尾插入数据，一开始每次插入数据都要申请节点，在队列满了之后，我们在队头删除数据，之后再要插入数据时我们就要判断要插入的节点数据是否为空，节点虽在，但内容数据被删掉了，此时需要status来存储节点的状态，记录空还是非空，比较麻烦。

数组：直接申请一块连续的空间，不需要像链表那样不断申请结点，也不需要指针来指来指去。定义两个变量，front 和 rear 分别指向队头和队尾，往 rear 指向的位置插入数据，之后 rear++，在 front 指向的位置删除数据，之后 front++。大体思路就是这样，操作比链表要简单。但是还有很多细节需要去补充调整，接下来跟着我的思路开始。

3.Q1：如何来判断队列是满的？

一开始 front 和 rear 都指向下标为0的位置，此时队列为空，每插入一次数据 rear 都要++指向下一个位置，因为是循环队列所以当队列插满的时候 rear 和 front 指向同一个位置 ，这时我们发现队列满时和队列为空时都是 rear == front ，那么该如何分辨队列满和为空时？

A1：如上图所示，我们多申请一个空间，一开始 front 和 rear 还是指向同一个位置（此时front 和 rear 相等，循环队列为空），假如我们要插入4（k）个数据为满，插入完最后一个数据时 rear 指向多申请的那个空间，此时队列满了，按照（rear+1）% （k+1）== front，为满，这样我们就可以分清何时为满何时为空了。

4.上代码！ //创建循环队列的结构 typedef struct { int* arr; int front; int rear; int capacity; } MyCircularQueue; //初始化循环队列 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); pst->arr = (int*)malloc(sizeof(int)*(k+1)); pst->front = pst->rear = 0; pst->capacity = k; return pst; } //判断队列是否为满 bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1) % (obj->capacity+1) == obj->front; } //向循环队列里面插入数据 bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->arr[obj->rear++] = value; //防止rear越界 obj->rear %= obj->capacity+1; return true; } //判断循环队列是否为空 bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->rear; } //删除元素 bool myCircularQueueDeQueue(MyCircularQueue* obj) { //队列不为空 if(myCircularQueueIsEmpty(obj)) { return false; } obj->front++; //防止front越界 obj->front %= obj->capacity+1; return true; } //取循环队列队头元素 int myCircularQueueFront(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } return obj->arr[obj->front]; } //取循环队列队尾元素 int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } //return obj->arr[obj->rear-1]; //但是当rear == 0时，指向队头第一个位置时，rear-1 == -1， //此时出现错误,需要我们特殊处理一下 int prev = obj->rear-1; if(prev == -1) { prev = obj->capacity; } return obj->arr[prev]; } //销毁 void myCircularQueueFree(MyCircularQueue* obj) { free(obj->arr); obj->arr = NULL; free(obj); obj = NULL; } /** * Your MyCircularQueue struct will be instantiated and called as such: * MyCircularQueue* obj = myCircularQueueCreate(k); * bool param_1 = myCircularQueueEnQueue(obj, value); * bool param_2 = myCircularQueueDeQueue(obj); * int param_3 = myCircularQueueFront(obj); * int param_4 = myCircularQueueRear(obj); * bool param_5 = myCircularQueueIsEmpty(obj); * bool param_6 = myCircularQueueIsFull(obj); * myCircularQueueFree(obj); */ 5.【注意】 在取队尾元素的时候，是取 rear-1 指向的元素，若 rear-1 == -1，我们就需要特殊处理一下，具体详见代码。在实现操作的时候我们要注意 front 和 rear 不能越界，obj->front %= obj->capacity，这样之后就从越界的位置变成下标为0的位置，如果没有越界，这样操作也不会改变 front 和 rear 的原始值。我们申请的空间是比要存储数据的空间多一个。我们定义一个 capacity 来保存要存储有效数据的个数。

这道题还是比较难的，我们需要多多思考细节思路+回顾敲代码。

完——

Look4You_Alberto Ciccarini、Beatrich_高音质在线试听_Look4You歌词|歌曲下载_酷狗音乐

（你真的会点开我精心分享给你的歌吗？）

至此结束！

我是云边有个稻草人

期待与你的下一次相遇。。。