循环队列的实现

 该题目来自力扣，具体要求如下：

 循环队列的实现：

1、构造一个循环队列。

构造循环的队列有两种方式，用顺寻表或者链表实现都可以，两者优势互补，这里重点讲解用顺序表实现。

按照题目要求，该循环队列的长度为K，还有头和尾。所以该队列的结构体中应该有这四种类型。

typedef struct {
    int* a;
    int front;
    int tail;
    int k;
 
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a=(int*)malloc(sizeof(int)*(k+1));
    q->front=q->tail=0;
    q->k=k;
    return q;
}

2、向循环队列插入一个元素。如果成功插入则返回真。

当队列容量满的时候，就不能插入，返回ｆａｌｓｅ，但是如何判断队列为满呢？假设按照要求开辟K个空间，那么当队列的头与尾重合时，队列的状态要么为空，要么为满，所以需要额外开辟出一个空间。

当开辟的空间为K个时：front等于tail,队列为空。

 当队列满时：front依旧等于tail。

 当额外开辟一个空间时：front等于tail，此时队列为空。

 当队列为满时，front和tail的关系为 (tail+1)%(K+1)。

 所以具体代码为：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
     //满了,不能在插了
     if(myCircularQueueIsFull(obj)) 
    {
        return false;
    }
    obj->a[obj->tail++]=value;
    obj->tail %=(obj->k+1);
    return true;
 
}

3、从循环队列中删除一个元素。如果成功删除则返回真。

当队列为空时，无法删除，所以需要返回false。

假设该队列的情况为图所示：当队列的头走到开辟空间的尾时，继续删除队列的头元素，那么需要队列的头转向空间的头，所以在删除时，需要将front%=(k+1),或者直接判断也可以。

 

 

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)) //空了，不能再删了
    {
        return false;
    }
    obj->front++;
    obj->front %=(obj->k+1);
    return true;
}

4、返回队列的头元素，如果队列为空，则返回-1；

直接返回即可，没有特殊的情况。

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

5、返回队列的尾元素，如果队列为空，则返回-1；

如果是tail不在下标为零的位置，那么直接返回的是 tail-1位置的数据，当tail在第一个位置时，队列的最后一个在下标为4的位置，这是在用tail-1，那么会造成非法访问。

 这种情况有两种方法解决，一种是用if判断，当tail在下标为0的位置时，直接返回下标为4的元素，另一种是用数学公式 直接用(tail+K)%(K+1)，无论tail在什么位置，都可以正常的返回。

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    /*if(obj->tail==0) //下标为0 特殊情况
      return obj->a[obj->k];    
      else
       return obj->a[obj->tail-1];  */
       int i=(obj->tail+obj->k)%(obj->k+1);
       return obj->a[i];
}

附：全部的代码

 
typedef struct {
    int* a;
    int front;
    int tail;
    int k;
 
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a=(int*)malloc(sizeof(int)*(k+1));
    q->front=q->tail=0;
    q->k=k;
    return q;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
     //满了,不能在插了
     if(myCircularQueueIsFull(obj)) 
    {
        return false;
    }
    obj->a[obj->tail++]=value;
    obj->tail %=(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;
    }
    /*if(obj->tail==0) //下标为0 特殊情况
      return obj->a[obj->k];    
      else
       return obj->a[obj->tail-1];  */
       int i=(obj->tail+obj->k)%(obj->k+1);
       return obj->a[i];
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
     return obj->front==obj->tail;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
     return (obj->tail+1)%(obj->k+1)==obj->front;
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->k=obj->front=obj->tail=0;
    free(obj);
 
}