力扣OJ题讲解——循环队列

今天我们一起来做一道关于队列的OJ题目，这是力扣题目622题，点击题目链接可以直接跳转，https://leetcode.cn/problems/design-circular-queue/

首先，我们看到要求，需要我们实现哪些功能？

我们需要设置队列长度K，队首元素，队尾元素，插入元素，删除元素，判断空，判断满。那这么多接口，我们要从哪里入手呢？我们现在做题无外乎要么用顺序表的方式，要么用链表的方式，使用两者其实都可以，今天我们就用顺序表的方式实现吧。既然使用顺序表也就是数组，那么我们要考虑一点，在什么情况下这个队列为空？要确定这个循环队列为空，那就需要保证，头元素的下标和尾元素的下标相等才可以，假设我们设头元素下标为front，back为尾元素下一个位置，因为我们要区分back=0时，到底是有一个元素还是没有元素的情况。即要保证front=back时，队列为空。

考虑了队列为空的情况，那什么时候循环队列满了呢？满了就是已经不能再放其它元素，也就是尾位置，back就要追上front了，也就是back=front吗？那我们想一想，队列为空的时候和队列为满的时候，都是front=back，我们要怎么区分这两种情况呢？

我们不妨设置队列长度K的时候多开一个空间，即k+1,我们保证k+1个空间最多只使用k个，留出一个位置，让back+1=front时为满队列。这样就能区分队列满和队列空的情况了。

下来我们开始做题。

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;

}

为什么我们要给开k+1个空间呢？原因我们在上面讲过了，就是为了让队列满的情况时back+1=front。

下来我们先把容易实现的接口先完成，先把什么时候为空，什么时候为满实现。

为空

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

为满

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->back+1=obj->front;//这样做合适吗？
}

我们要考虑到，这是一个循环队列，下面这种情况能满足吗？

back要一直往后走吗？显然不是，这是一个循环队列，当back走到k时，下一次就要回到起点，那怎么表示呢？我们不妨这样表示，(obj->back+1)%(obj->k+1)==obj->front，这个队列一共有k+1个空间，我们知道，如果一个小的数%一个比自己大的数是不会改变值的，所以，如果back+1=k+1,此时，back就要回到起点了。所以判断队列满我们可以这样写

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

下面我们写插入接口

这是一个bool类型，也就是要返回true和false,那什么时候要返回false呢？注意这是往队列插入元素，如果队列已经满了，我们就插不了元素了。剩下就可以正常插入了，直接让obj->a[obj->back]=value即可，再让obj->back++。注意到这里，我们还要需要检查back有没有超过队列空间的大小，即我们需要在后面让obj->back%=obj->k+1;即

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

队列删除

删除接口同样是bool类型，我们要判断什么时候删除失败？当然就是队列为空的时候删除失败，我们要先检查队列是否为空，再删除，删除非常简单，直接让front++就可以了，front一直在++,有没有可能front也会超出队列的空间大小？当然有可能，所以我们也需要对front检查一下，即obj->front%=obj->k+1;

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

下面就是返回对头元素

题目里说了，如果队列为空就返回-1，这种情况我们也要处理一下，其余就直接返回obj->a[obj->front]即可。

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

队尾元素

同样我们也要处理一次队列为空返回-1的情况，然后直接返回obj->a[obj->back-1]可以吗？

我们思考一下，如果back=0呢？我说的不是队列为空时，因为为空时我们已经处理了，我说的时当back已经走了至少一轮重新回到起点的情况，此时的back-1就成-1了，那我们怎么处理呢？我们要知道，这种情况下的back时已经被取模了k+1后，那我们不妨可以给back-1+k+1再给它取模k+1;即(obj->back-1)+(obj->k+1)%(obj->k+1);怎么理解这个公式，还是那句话，back-1不可能大于k+1，一个数%比他小的数值不变，(a+b)%b,如果a比b小且a是正数，那这个值是不变的，这一种情况也就对应了我们此处back!=0的情况，如果back=0,尾元素就在k的位置，那back-1就是-1，他再加上k+1再%k+1要比k+1小，所以结果就是k那个位置。

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

到这里这道题就大功告成了，此时我们运行，报了一个这样错误

是因为，我们在前面调用了就很多次队列为空为满的情况，也没有声明，所以我们可以把判断队列为空，为满挪到插入接口前面就可以啦。