商城网站开发文档国家建设执业资格注册中心网站

循环队列是我们可以对队列有更深一步的理解的题目，而且可以进一步加强其他方面的知识（例如对循环数组的取模运算，指针的解引用），是个蛮不错的巩固习题，话不多说，进入正题。

链接在此：设计循环队列
强烈建议先自己做一遍，直接看的话可能会比较不知所云

本题可以使用 数组或链表来设计，本篇文章都会涉及到
做这题时会遇到很多难点
先说结论：此题的难点在于如何判断数组的 空与满，不管是链表还是数组，实现此问题都是难点。
在数据结构中，我们通常在解决此问题时都是选择多设置一个位置，back指向当前元素的下一个。
但多出来的位置不是不用，例如：

这样可以比较好的解决此类问题。

利用数组设计：

思路：

已经有了上述的前置知识
我们就可以比较轻易地判断空与满，数组中的front和back下标指向同一个位置时是空，那么什么时候会满呢？
当back的下一个为front时就为满，即back+1 == front，

但是如果back在front后边，就需要我们的比较灵活的运用取模运算
在上边我们说到back+1 == front时为满，但是在上图中，我们发现back+1并不是front，而是超出了数组，
我们说过，会定义N+1个空间，N是元素个数，经过思考，我们会发现N就是back的下标，N+1就是back+1位置的下标，
那我们（back + 1）% (N + 1) == front时就是满
代码中剩下的取模运算也都大同小异

代码实现：

typedef struct {int* arr;int front;int rear;int N;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return (obj->front == obj->rear);
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->rear + 1 ) % (obj->N + 1) == obj->front;
}MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));ret->arr = (int*)malloc(sizeof(int)*(k+1));ret->front = 0;ret->rear = 0;ret->N = k;return ret;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->arr[obj->rear] = value;obj->rear++;//防止rear出界obj->rear %= (obj->N + 1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;//防止front出界obj->front %= (obj->N + 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;}//此处可以不用取模，if与else判断也可以return obj->arr[(obj->rear-1+(obj->N+1))%(obj->N+1)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}/*** 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);
*/

一一一一一一一一分割线一一一一一一一一
持续更新中…

利用链表设计：

思路：

代码实现：