[LeetCode]-622. 设计循环队列

662. 设计循环队列

题目

思路

代码

662. 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）https://leetcode.cn/problems/design-circular-queue/

题目

设计你的循环队列实现。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

示例：

思路

开辟一个大小为k+1的数组，可存放k个有效元素，队列头front和队列尾rear为数组下标，边插入删除数据边移动front和rear的位置，超过数组尾时回到数组头位置形成循环达到循环队列的效果。

实现循环队列效果如下：

难点1：

rear在数组尾时插入数据：rear刚好到数组尾时，要在rear上插入数据，rear要循环回到数组头的位置，而不是直接rear++就完了。

解决方法：

取模思想：rear++后模上数组长度k+1，超过数组尾后回到数组头如下图：

难点2：

front在数组尾时删除数据：front刚好在数组尾位置上时，要从队头front删除元素，front后移超过数组尾了。

解决方法：

取模思想：front超过数组尾时,模上数组长度k+1，front回到数组头位置如下图：

难点3：

取队尾元素：当rear在数组下标为0的位置时，rear-1到-1的位置了，而队尾元素在数组尾的位置。

解决方法：

加 if 语句，当rear在下标为0位置，取队尾元素位置为下标k+1。
取模思想：取下标时（rear+（k+1）-1）%（k+1）如下图：

代码

（下面函数里面有要调用的函数如探空、探满这些，这些函数要放前面些，先声明再使用）

typedef struct {
    int* a;//起始地址
    int front;//数组下标
    int rear;//数组下标
    int k;//有效数据个数
} MyCircularQueue;


//构造器
MyCircularQueue* myCircularQueueCreate(int k) {
    //结构体开辟空间
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //数组开辟空间,多开辟一个可区分满和空
    obj->a=(int*)malloc(sizeof(int)*(k+1));
    //开始是空的状态
    obj->front=obj->rear=0;
    //传入的数（有效个数）给给k
    obj->k=k;

    return obj;
}
//探空和探满尽量位置往前放
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%(obj->k+1)==(obj->front);
}

//插入一个元素 成功返回真
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //判断是否满
    if(myCircularQueueIsFull(obj))
        return false;
    //插入rear位置
    obj->a[obj->rear]=value;
    obj->rear++;
    //模上一个数组的长度，rear超过到数组尾可以循环回到数组头
    obj->rear%=(obj->k+1);
    return true;
}
//删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //判断是否为空
    if(myCircularQueueIsEmpty(obj))
        return false;

    //队头front往后移 ++front
    ++obj->front;
    //取模可在超过队尾时回到队头，取模不影响中间的移动
    obj->front%=(obj->k+1);
    return true;
}

//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //探空
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        //模上k+1  rear+(k+1)-1 % (k+1)
        return obj->a[(obj->rear+obj->k) % (obj->k+1)];
}


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