设计循环队列，解决假溢出问题

什么是假溢出？

当我们使用队列这种基本的数据结构时，很容易发现，随着入队和出队操作的不断进行，队列的数据区域不断地偏向队尾方向移动。当我们的队尾指针指向了队列之外的区域时，我们就不能再进行入队操作了，而此时由于队头已经偏离原来位置，也就意味着实际上队列并没有满。这种实际上还有空间，但是却发生了溢出的现象就称为假溢出现象。

假设有以下队列，初始元素为1、2、3、4、5，队头元素是1，队尾元素是5.

当我们弹出队头元素两次得到队列：

这个时候top指针向右边偏移，如果再进行入队操作我们会发现rear指针已经不能向后移动了，而此时队列并没有满（top前面还有空间）。

这就是假溢出。

如何解决假溢出问题？

为了避免假溢出问题，我们需要对队列进行优化--循环队列。

对于前面的问题，我们发现导致假溢出的主要问题就是尾指针rear不能指向可以存放空间的地址，换句话来说就是不能指向前面已经出队了元素的地址。针对这一问题，我们整个队列看成一个可以循环的环状结构，指向队头队尾的指针往后走还能回到原来的位置。

 这样一来，前面已经出队元素的空间我们依旧可以存放元素，也就解决了假溢出的问题。（这里rear指向队尾元素的下一个元素）。

模拟循环队列

首先假设我们队列的最大存储数据个数为k。

用一个数组来模拟循环队列，并且初始化容量为k+1,队头队尾指针都指向下标为0的元素地址

为什么容量要多一个呢？

为了更好的区分队列为空和队列已满。

 

如何判断循环队列是否为空？

if(top==rear)为真则队列为空

如何判断循环队列是否为满？

由于我们多开辟了一个元素的空间，且这个空间不存放元素，也就意味着，如果已经存了k个元素，此时的rear指向这个空的区域，rear指向空间的下一个空间的元素被top指针指向。

if((rear+1)%(k+1)==top)//真则队列为满

如何求得循环队列的元素个数？

num=(rear+k-top)%(k+1)//num为循环队列元素个数

由于rear指针可能在top指针的前面，所以我们不能直接使用rear-top.

那么我们可以这么想，之所以rear会出现在top前面，是因为rear已经走了一圈了（假设只多走了一圈），那么rear移动的总距离就是当前元素位置加队列长度，top移动的距离就是当前下标。

力扣面试题：

622. 设计循环队列https://leetcode.cn/problems/design-circular-queue/

代码：

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