循环队列--数组实现_循环队列数组实现

622. 设计循环队列 - 力扣（Leetcode）

利用数组的特性可以方便在代码实现的。

这里我们想一个问题，如何判断空与满。

front从顺时针到rear的数据才为有效数据

如果开辟K个空间，保存K个有效数据。

队满情况

入数据，rear向后移动，当rear==front时，环形队列为满

队空情况

出数据，front向后移动，直到与rear相等时为空

继续pop

观察判空与判满，会发现无论时空还是满 都是rear==front

所以我们需要多开辟一段空间，用来表示队列的尾部，不存储有效数据

如果开辟K+1个空间，保存K个有效数据。

队满情况

这时候满的情况为rear下一位置==front就为满情况。

当rear+1==front时（特殊情况后面讲）队列为满情况，不在插入数据。

队空情况

出队列，front开始移动

继续pop，继续移动

当front移动到rear指向的空间时，队列为空，不可再删除

---

各个接口实现讲解

声明结构体类型

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

a为数组，front队头位置，rear队尾位置，k为可使用空间数量

初始化Init

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

1. 开辟一个结构体空间，初始化front与rear位置=0，参数k赋值到有效空间k中；

2. 开辟队列所需数组，参数给的k为存放有效所需的空间个数，但我们要多开辟一个空间当作尾。

入列Push

这里的入列，我们前提条件为队列不为满的情况，进行分类讨论

看以下代码

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

是对的吗？不是

将数据放入以rear索引的空间后，rear向后移动一位将下一个位置定位尾

这样看似没有问题，但是如果再push前已经出现pop过，代码就会可能出问题

push (5)；

这样看似乎没有什么问题

但是数组rear+1超出了数组的范围，越界访问

真实情况是

push(5);

超出范围

如何改该bug呢？

将rear模上k+1的值就是rear下一步

正确代码：

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->rear++]=value;
    obj->rear%=(obj->k+1);//当rear超出范围模上k+1，就可以归为0，如果rear为超出k+1就不受影响
        return true;
}

出列Pop

提示：front开始向右，到rear的才是有效数据，rear如果在front前也是从front向右，到数组底后，然后从索引0到rear，这2段位有效数据。

先声明数据不为空，

在入列时我们已经知道了存在特殊情况，所以我们现在，直接分类

普通情况front+1不超出数组范围

pop()：front向后移动一位，

完成

特殊情况front+1超出数组范围

pop()：front向后移动一位，

这样的front也要进行取模操作

完整Pop代码

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
   if(myCircularQueueIsEmpty(obj))
        return false;
    ++obj->front;
    obj->front%=(obj->k+1);//和rear原理一样
    return true;    
}

读取队尾

先确定不为队列不为空

分类讨论，如果尾索引为0，与尾索引不为0

不为0

rear-1就是队尾元素值：1

不为0

这时候队尾元素为数组索引k值：9

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
//分类讨论
    if(obj->rear==0)
    {
        return obj->a[obj->k];
    }
    else
    {
        return obj->a[obj->rear-1];
    }
//减一加k+1模k+1
    //return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)]
}

读取队头

先确定不为队列不为空

数组front索引就是对头元素

代码为

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

队列判空

之前提到过，简单描述：如果front==rear时直接为空；

看代码

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

队列判满

根据前面的情况，分类讨论，当尾为数组最后一个元素，不为最后一个元素

不为最后一个元素

直接判断rear+1==front

为最后一个元素

需要判断0==front；

接口代码：

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //直接分类讨论
    if(obj->rear+1==obj->k+1)
    {
        if(0==obj->front)
        {
            return true;
        }
    }
    else
    {
        if(obj->rear+1==obj->front)
        {
            return true;
        }
    }
    return false;
    //取模后判断
    //return (obj->rear+1)%(obj->k+1)==obj->front;
}

销毁Free

先销毁结构体内指针指向的数组，在销毁结构体。

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

---

谢谢观看