含泪写完！我终于学会了循环队列

2024-03-22 21:36:40

文章目录

Leetcode栈刷题——设计循环队列
全部代码：
总结：

Leetcode栈刷题——设计循环队列

[622. 设计循环队列 - 力扣（LeetCode） (leetcode-cn.com)]

判断是否为空

判断是不是空就十分简单了，直接判断first和tail是否是相同的就可以

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

判断是否是满的

判断是不是满的就有一点复杂了，因为这里我们要判断的是tail的下一个是不是first

就以本例子来说：

tail的下一个就是first，说明满了。

所以，我们只需要判断tail的下一个是不是first就可以了。

但是，还是需要注意一种特殊情况：

tail加1就是4了，超出了界限。所以当tail+1是k+1的时候，让tail=0；

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int rearnext = obj->rear + 1;
    if (rearnext == obj->size + 1)
    {
        rearnext = 0;
    }
    return rearnext == obj->first;
}

插入数据

判断队列不是空，就可以进行插入了。

让该值赋予队列的最后一个值。

但是要注意一个特殊情况：

这是原来情况：

弹出1并插入4后：

所以我们要让tail=0，移动到前面去：

这是一个非常值得注意的一点：

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

退出数据：

对于这个出栈来说：就是简单的first先后移动。

但是，也还是要注意一种特殊的情况：

就上面的这种情况来说：

要把4推掉，first就等于k+1了

所以要把first移动到前面去。

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->first++;
        if (obj->first  == obj->size + 1)
        {
            obj->first = 0;
        }
        return true;
    }
}

返回头数据

返回头数据也是非常的简单了，直接返回first的值就可以了。

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->first == obj->rear)
        return -1;
    else
        return obj->a[obj->first];
}

返回尾数据

返回尾数据就有一些复杂了。

因为rear的位置一直是当前位置的下一个值。

所以，要返回尾数据，我们就要得到尾数据的前一个值。

但是，还有一种特殊的情况：

tail的下标是0，prev就是-1，不符合情况，

所以，这种情况下，我们就要让prev是k了。

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
    {
        int tailprev = obj->rear - 1;
        if (tailprev == -1)
        {
            tailprev = obj->size;
        }
        return obj->a[tailprev];
    }
}

全部代码：

typedef struct {
    int* a;
    int size;//长度
    int first;
    int rear;
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj);
MyCircularQueue* myCircularQueueCreate(int k) {
    //malloc了一个循环队列
    MyCircularQueue* tmp = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //malloc一个数组a
    tmp->a = (int*)malloc(sizeof(int) * (k + 1));//多增加一个空的
    tmp->size = k;
    tmp->first = 0;
    tmp->rear = 0;
    return tmp;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->first == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    int rearnext = obj->rear + 1;
    if (rearnext == obj->size + 1)
    {
        rearnext = 0;
    }
    return rearnext == obj->first;
}

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

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        obj->first++;
        if (obj->first  == obj->size + 1)
        {
            obj->first = 0;
        }
        return true;
    }
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->first == obj->rear)
        return -1;
    else
        return obj->a[obj->first];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
        return -1;
    else
    {
        int tailprev = obj->rear - 1;
        if (tailprev == -1)
        {
            tailprev = obj->size;
        }
        return obj->a[tailprev];
    }
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

总结：

不画图我是不可能会直到这么多特殊情况的，

所以，一定要多画图。

没画图的时候，我认为这个题的逻辑怎么这么难！

但是，画完图，给出具体的例子，我发现其实一点都不难了！

真的是太神奇了！

所以，

以后要习惯于画图。

找个具体的例子。

画好模板。

找好特殊情况。

我相信我自己可以的！

码农公寓