速学数据结构 | 循环队列怎么写才最高效？只需要掌握这些技巧

鸽芷咕

发布于 2023-12-25 14:59:18

1210

发布于 2023-12-25 14:59:18

文章被收录于专栏：C++干货基地C++干货基地

🎬 鸽芷咕：个人主页 🔥 个人专栏:《Linux深造日志》《C++干货基地》

⛺️生活的理想，就是为了理想的生活!

文章目录

📋 前言
一、什么是循环队列？
二、如何实现循环队列？
- 2.1 循环队列的结构
- 2.2 循环队列的初始化
- 2.3 如何检查队列是非为空
- 2.4 如何检查队列是否满了
- 2.5 循环队列如何插入数据
- 2.6 循环队列如何删除数据
- 2.7 获取循环队列头元素
- 2.8 获取循环队列尾元素
- 2.9 如何销毁循环队列
三、循环队列练习
- - 循环队列结构代码：
  - 循环队列练习题
📝全篇总结

📋 前言

🌈hello！各位宝子们大家好啊，今天给大家带来循环队列的详细解析，队列我们会写了那么循环队列呢？今天这个还是有点难度的 ⛳️学完之后保证你对队列又会有一个更清晰的认识。让你彻底拿捏队列循环队列一搞完我们的队列学习就告一段落了。 📚本期文章收录在《数据结构&算法》，大家有兴趣可以看看呐！ ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝！

一、什么是循环队列？

队列我们都自动是数据结构中类似排队一样的结构，主要满足：先进先出的特点。而循环队列的话顾名思义就是把头和尾链接起来循环这样就是循环队列了。

下面我们就来看一下他大概得物理图吧！

上面是为了方便大家理解而做的图，而实际的循环队列是这样的

二、如何实现循环队列？

这里我们先看一下力扣上面的题目要求我们，要实现循环队列要实现的功能然后再进行逐个实现就好了。

循环队列链接：622. 设计循环队列

2.1 循环队列的结构

首先我们需要考虑的就是循环队列的结构，很多人可就会想到使用链表去实现循环队列但是这里有俩个问题：

循环队列如何判空和满？
如果让 rear 指向有数据的那么插入第一个数据的时候是否为空？
如果让rear 指向数据后面的空间那么尾元素该如何去找？
如果 rear 满了如何判定是否为空

所以为了解决这种情况我们选择试用数组的方式实现，多开一个元素来实现循环链表就完美解决问题了：

使用 下标访问 解决找不到前一个元素的问题
而假溢出问题：我们多开了一个空间可以解决空和满的问题

2.2 循环队列的初始化

好了上面我们已经知道了循环队列用哪种方式更优，那么接下来就是设计循环队列的结构了：

首先我们需要一个 int* 的指针来开辟数组
然后需要一个头 front 当下标
需要一个尾 rear 来当尾数据的下一个下标
需要一个 k 来接收开辟队列的长度

📚 代码演示：

ypedef 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;
    obj->k = k;

    return obj;
}

2.3 如何检查队列是非为空

这个就更加简单我们我们前面说了：

只要 front == rear 就为空，因为没有数据俩个都是同一个下标。

📚 代码演示：

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

2.4 如何检查队列是否满了

如何检查队列是否满了，就需要判断一下 rear 的下一个是否为 front 了：

这里需要注意的是 rear 的过界问题，如何让下标回归正常
其实只需要 模除 一下就好了

📚 代码演示：

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

2.5 循环队列如何插入数据

循环队列插入数据的话，首先要判断是否为满就然后插入就行了：

然后 ++obj->rear 了之后要考虑一下 rear 在最后一个位置的情况
模除一下就好了

📚 代码演示：

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

    return true;
}

2.6 循环队列如何删除数据

删除数据也是一样，循环队列如果空了就返回 false 没空 front++ 就好了：

同样要注意控制好front的边界值

📚 代码演示：

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

    
}

2.7 获取循环队列头元素

获取头元素就很简单啦，只需要使用 front 来当下标访问就好了

📚 代码演示：

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

2.8 获取循环队列尾元素

这里就需要考虑很多问题，rear是尾元素的下标的一个一个下标：

我们需要要考虑如果 rear 指向最后一个空间怎么办？
rear 指向中间怎么办? 如何回到上一个
rear 下标为零的时候如何回到他的上一个下标

📚 代码演示：

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

2.9 如何销毁循环队列

销毁就很简单了，先 free 掉我们动态开辟的空间，在free掉循环队列的空间就好了：

📚 代码演示：

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

三、循环队列练习

循环队列结构代码：

📚 代码演示：

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

} MyCircularQueue;

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

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

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

    return obj;
}

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

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    ++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
        return obj->a[(obj->rear+obj->k)%(obj->k+1)];
}



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

循环队列练习题

这里我们可以去力扣一下检验和练习一下：

这章内容还是比较有难度的，可以多琢磨琢磨
力扣题目链接：循环队列

📝全篇总结

☁️ 把本章的内容全部掌握，铁汁们对于队列的理解就更上一层楼了！ 看到这里了还不给博主扣个： ⛳️ 点赞☀️收藏 ⭐️ 关注！ 💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖 拜托拜托这个真的很重要！ 你们的点赞就是博主更新最大的动力！ 有问题可以评论或者私信呢秒回哦。