实战oj题——设计循环队列

前言：今天我们来实现循环队列。

在这里插入图片描述

各个接口的实现

创建队列：

typedef struct {int* a;int front;int back;int k;} MyCircularQueue;

我们的队列是由数组储存的，所以我们队列中得定义一个数组，front代表我们的首元素，back指向的是我们数组中的下一个元素，k则是长度。

初始化队列：

MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->front=0;obj->back=0;obj->k=k;return obj;
}

判断队列为空：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->back;}

front代表我们的数组的头元素下标，back指向我们的队尾元素下标的下一个，如果我们的front=back，那么为空。

判断队列是否为满：

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1)%(obj->k+1)==obj->front;}

back+1==front的话就为满，如果我们的循环队列多循环几次，那么我们的下标大小就会大于我们的数组的长度，所以我们需要模上我们的长度，如果我们的back+1模上k+1的 ==front那么就为满。

队列插入数据：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj-> back++;obj->back%=(obj->k+1);return true;    
}

我们的back指向的是我们队尾元素的下一个，所以我们在给队列赋值之后，但是我们的back可能大于数组的长度，所以我们的back需要模上数组的长度。

队列删除数据：

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;++obj->front;obj->front%=(obj->k+1);return true;    
}

我们只要front++访问下一个就能将队列首元素删除，我们现在的front就是首元素的下标，我们的front同样可能大于数组长度，我们同样需要模上数组长度。

返回队列首元素：

int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];}

获取队尾元素：

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];}

我们的back指向的是队尾元素的下一个元素，我们的队尾元素的下标就为back-1，如果我们的back为0的话就会引起错误，所以我们加上一个数组长度，我们的队尾元素的下标也可能大于数组长度，所以我们还要模上一个数组长度。

完整代码展现：

typedef struct {int* a;int front;int back;int k;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int*)malloc(sizeof(int)*(k+1));obj->front=0;obj->back=0;obj->k=k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->back;}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1)%(obj->k+1)==obj->front;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj-> back++;obj->back%=(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->a[obj->front];}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[(obj->back-1+obj->k+1)%(obj->k+1)];}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}