
typedef struct {
    //数组实现
    int front;
    int tail;
    int k;
    int *a;
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front=0;
    cq->tail=0;
    cq->k=k;
    cq->a =(int*)malloc(sizeof(int)*(k+1));
    
    return cq;
}

那么我们在构造队列时，需要注意的就是需要开辟 K+1 个空间，最后一个不能忘记的是将新开辟的空间返回。

2.2向队列中插入元素

首先，我们需要判断当前队列是否为满，如果当前队列为满的话，则直接返回false，否则进行插入操作。

如下代码所示，当队列不为空，然后进行插入操作时。首先我们将该元素插入尾指针 tail 表示的数组 a ，然后将尾指针自增 1 ，最后需要对 k 的值进行取模操作，因为这里表示的是循环队列，我们需要将其限制在一定的范围内。

而这里的取模也非常简单，就是将 tail 对 k+1 进行取模，但是需要注意这里只有 obj->k ，没有单独的 k 。

2.3删除队列中元素

对于顺序表实现的队列来说，删除元素是比较简单的，但是我们需要删除的是队头的元素，因为队列的特性就是“先进先出”。所以这里我们判断完队列中不为空的时候，只需要将 front 自增 1即可，这也是我们数组中一般进行删除的方式。

当然一定不能忘记的是对其取余，保证 front 限制在队列长度的范围内。

2.4获取队尾和队首元素

那么对于获取队尾和队首元素，相对来说是比较简单的。但是这里需要注意的是，两个指针 front 和 tail 在每次删除或者插入元素之后，会自增。

以及题目中要求的。如果获取不到，则直接返回 -1。

2.4.1获取队尾元素

如下图所示，当前队尾元素是 tail 指针的前一个元素，所以这里我们需要对 tail 做一个修正之后才能得到队尾元素：（tail+k）%（k+1）

2.4.2获取队首元素

那么对于获取队首元素是相对比较简单的。直接返回当前 front 所在的元素即可。

2.4.3代码实现

两个接口的代码实现如下所示：


int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[obj->front];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    //因为tail总是指向最后一个元素后面的空位置
    //所以需要找tail之前的那个位置上的元素
    int i=(obj->tail+obj->k)%(obj->k+1);
    return obj->a[i];
}

2.5判空判满接口

2.5.1两种做法实现

如下图，我们可以看出，之前我们多开辟一个空间的作用就有了，如果我们没有多开辟一个空间，那么最开始没有数据的时候，以及数据满的时候，front 和 tail 指向的是同一个地方。

这样的表示方法，我们怎样去判断当前队列是否为空或者满呢？没法判断的，所以我们需要多开辟一个空间。

2.5.2正确做法

2.5.3代码实现


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

2.6释放队列

开辟的两个指针，都需要释放哦！

源码实现


typedef struct {
    //数组实现
    int front;
    int tail;
    int k;
    int *a;
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->front=0;
    cq->tail=0;
    cq->k=k;
    cq->a =(int*)malloc(sizeof(int)*(k+1));
    
    return cq;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //如果为满，返回false
    if(myCircularQueueIsFull(obj))
        return false;
    //否则，添加元素，然后tail后移一位，如果超出数组范围，进行取模
    obj->a[obj->tail]=value;
    obj->tail++;
    obj->tail %= (obj->k+1);
 
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
     if(myCircularQueueIsEmpty(obj))
         return false;
    //有元素，删除
    //删除数组元素，不用free，只需要将其覆盖
    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;
    //因为tail总是指向最后一个元素后面的空位置
    //所以需要找tail之前的那个位置上的元素
    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);
    free(obj);
}

好的，那么对于循环队列的题目就结束啦，如果小伙伴们有问题，可以留言评论哦！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/590133