这是Leetcode中的第622题,大家可以做一下:
一.解题思路:
1.循环?怎么循环呢?
2.为何要多开一个空间?
初始状态我们将front和rear都设置为0,此时队列为空
那么可能很多小伙伴会仍然像非循环队列那样让front指向队首元素,rear指向队尾元素的下一个,
入队列:arr[rear]=value;rear++；
出队列:front++;
也就是这样:
中间过程图：此时0,1,2,3,4进入队列
最终状态
图中0,1,2,3,4,5,6,7依次进入队列,正好也表示数组的下标
此时队列满了,不过:front=rear
此时front=rear,本该表示队列为空,但是现在队列是满的,那我们应该如何解决这个问题呢?
常见的方法有两种：
1.留一个空位, front和rear重合为空，front在rear前面一个位置为满
2.用一个变量记录队列中元素数量
这里我们采用第一种方法:
3.怎么判空,怎么判满?
判空:front==rear
判满:(rear+1)%(队列长度)==front
二:本题特殊之处
所以有了下面的代码:
//取队尾元素的函数 int myCircularQueueRear(MyCircularQueue* obj) { //题目要求:如果队列为空,返回-1 if(myCircularQueueIsEmpty(obj)) { return -1; } //rear==0 if(obj->rear==0) { return obj->arr[obj->k]; } //rear!=0 else { return obj->arr[obj->rear-1]; } }
代码如下:
int myCircularQueueRear(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return -1; } int ret_i=(obj->rear+obj->k)%(obj->k+1); return obj->arr[ret_i]; }
三.本题代码(C语言实现)
typedef struct { int* arr; int front; int rear; int k; } MyCircularQueue; MyCircularQueue* myCircularQueueCreate(int k) { //两次malloc MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); cq->arr=(int*)malloc(sizeof(int)*(k+1)); cq->front=0; cq->rear=0; cq->k=k; return cq; } //Front函数和Rear函数要判空和判满,前置声明一下 bool myCircularQueueIsEmpty(MyCircularQueue* obj); bool myCircularQueueIsFull(MyCircularQueue* obj); bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if(myCircularQueueIsFull(obj)) { return false; } obj->arr[obj->rear]=value; obj->rear++; //防止假溢出,实现循环,进行取余操作 obj->rear%=(obj->k+1); return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if(myCircularQueueIsEmpty(obj)) { return false; } obj->front++; //防止假溢出,实现循环,进行取余操作 obj->front%=(obj->k+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; } int ret_i=(obj->rear+obj->k)%(obj->k+1); return obj->arr[ret_i]; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front==obj->rear; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return (obj->rear+1)%(obj->k+1)==obj->front; } void myCircularQueueFree(MyCircularQueue* obj) { //两次free free(obj->arr); free(obj); }
以上就是循环队列的讲解,希望能对大家有所帮助!
