Leetcode:622. 设计循环队列 题解【具详细】

目录

一、题目：

二、思路详解：

1.循环队列的存储定义

2.循环队列的创建

3.循环队列的判空与判断情况

(1) 循环队列的判空:

 (2) 循环队列的判满

4.循环队列元素的插入

5.循环队列元素的删除

6.获取队头元素

7.获取队尾元素 

8.循环队列释放

三、完整代码展示：

一、题目：

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

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

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

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

难度：中等

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

题目解析：就是根据题中给的接口进行函数的实现。要求我们实现一个循环队列。

用心阅读下方会有很大的收获。 

二、思路详解：

1.循环队列的存储定义

首先我们需要定义出一个循环队列的存储定义，这里采用的是使用动态数组来进行模拟循环队列，根据题中给出的接口返回类型，我们可以知道循环队列的数据类型为int 。

其次，还需定义两个记录数组的下标，一个记录队列的队头，另一个记录队列的队尾(也就是指向要入队的下一个元素的位置)。另外还要提供一个表示要存储数据的具体个数。

如图：

代码：

//采用动态数组的形式来模拟循环队列
typedef struct {
    int* a;     //指向数组
    int front;  //队头
    int tail;   //队尾
    int k;      //数据个数
} MyCircularQueue;

2.循环队列的创建

循环队列的创建，先使用malloc进行创建一个 循环队列空间

接着根据给的数据个数k让指针a指向一个动态数组，在分别对front,tail,k进行初始化，注意tail = 0表示要存放的下一个数据元素的位置，对动态数组a开辟空间的时候要多开辟一个空间，避免假溢出的现象。最后一定要返回之前创建的循环队列。

代码：

//创建长度为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    //使用动态内存函数来申请内存
    //这里多申请一个空间的目的是防止假溢出
    //使用malloc创建一个循环队列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //为循环队列里面的指针a ,让a指向一个长度为k+1的数组
    obj->a= (int*)malloc(sizeof(int)*(k+1));
    obj->front = 0; //队头从数组的下标0开始
    obj->tail = 0; //队尾指向下一个元素
    obj->k = k; //队列的长度为k
    return obj;
}

物理存储情况，如图：

但是我们一般会到其循环的逻辑结构，逻辑存储，如图：

 3.循环队列的判空与判断情况

循环队列的插入和删除是不可避免的，当这之前就需要先完成判和判满的接口。注意：一定要把判空和判满的函数实现放在队列插入和删除函数实现的前面。

(1) 循环队列的判空:

根据函数的返回类型是bool，空我们就返回true ,否则返回false。

  • isEmpty(): 检查循环队列是否为空。

因为这里采取的是通过动态数组来模拟循环队列，所以队列空的条件就是当front == tail 的时候，此时的循环队列就是空的。

如图：

代码：

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //队空，就是队头与队尾相同时
    return obj->front == obj->tail;
}
 (2) 循环队列的判满

 同样根据函数的返回类型是bool，空我们就返回true ,否则返回false。

  • isFull(): 检查循环队列是否已满。

什么时候会满呢？当(tail+1)%(k+1) == front,就是队尾下标加1模开辟空间的个数 

可能很多会对为什么要多开辟一个空间，原因就在这：对于队列的判满的情况，

当没有创建的额外空间，队列只有数据10 和 11 的情况下，

像上图就是假溢出现象，这个队列并没有满。

总的来说：

循环队列为了区分队列的空和满，需要额外增加一个空的元素来占据队列的一个位置，这样队列满的状态就可以通过头尾指针相邻且不重合来判断，而不会出现头尾指针重合但队列实际上并不满的情况。同时循环队列需要对头尾指针进行模运算，如果没有额外的空间，那么当队列最后一个元素占据了数组最后一个位置时，下一个元素就会从数组的第一个位置开始，这样就无法正确进行模运算，而增加一个空的元素可以解决这个问题。

 代码：

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

 4.循环队列元素的插入

  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

插入前判断是否满，满就返回false,接着就是数据的插入，插入后，对tail下标进行取模(因为是反复利用原来的空间，还有就是避免溢出)，插入成功就返回true。

 代码：

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //插入元素前先进行判断是否满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //插入元素使用尾插
    obj->a[obj->tail] = value;
    obj->tail++;
    //避免tail的下标越界
    obj->tail%=(obj->k+1);
    return true;
}

5.循环队列元素的删除

 删除前，要进行判断是否为空。队头减一，进行删除，删除后取模。

  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

 代码：

//出队
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //删除元素队列不能为空
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    //出队，头删
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
}

 6.获取队头元素

获取前进行判断，是否为空。

Front: 从队首获取元素。如果队列为空，返回 -1  

  代码：

//获取队首元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //队列不能为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1; //队空返回-1
    }
    return obj->a[obj->front];
}

7.获取队尾元素 

获取前进行判断，是否为空。

Rear: 获取队尾元素。如果队列为空，返回 -1  

  代码：

//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //队列不能为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1; //队空返回-1
    }
    //注意当tail = 0的情况
    return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
}

解释一下 上述最后一行代码：

重点：

首先tail是指向要存放下一个元素的位置，找队尾元素时，tail要进行-1。

 因为数组下标最小是从0开始的，当tail ==0且队列不为空的情况下，上方代码obj->tail-1,就会造成0-1 == -1的情况。上方采用(obj->tail - 1+ obj->k+1)%(obj->k+1)就可以完美的避免，当然

其实可以写成

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

8.循环队列释放

 因为用malloc开辟的动态内存空间，为了避免内存泄漏，我们还要释放内存。注意释放的顺序。

 代码：

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

三、完整代码展示：

 代码： 


//采用动态数组的形式来模拟循环队列
typedef struct {
    int* a;     //指向数组
    int front;  //队头
    int tail;   //队尾
    int k;      //数据个数
} MyCircularQueue;

//创建长度为k的循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    //使用动态内存函数来申请内存
    //这里多申请一个空间的目的是防止假溢出
    //使用malloc创建一个循环队列
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //为循环队列里面的指针a ,让a指向一个长度为k+1的数组
    obj->a= (int*)malloc(sizeof(int)*(k+1));
    obj->front = 0; //队头从数组的下标0开始
    obj->tail = 0; //队尾指向下一个元素
    obj->k = k; //队列的长度为k
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //队空，就是队头与队尾相同时
    return obj->front == obj->tail;
}

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

//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //插入元素前先进行判断是否满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    //插入元素使用尾插
    obj->a[obj->tail] = value;
    obj->tail++;
    //避免tail的下标越界
    obj->tail%=(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; //队空返回-1
    }
    return obj->a[obj->front];
}

//获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //队列不能为空
    if(myCircularQueueIsEmpty(obj))
    {
        return -1; //队空返回-1
    }
    //注意当tail = 0的情况
    return obj->a[(obj->tail - 1+ obj->k+1)%(obj->k+1)];
}

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

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/178827.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

frp内网穿透配置以及相关端口、过程解释

frp内网穿透配置以及相关端口、过程解释

介绍 假设现有外网笔记本、云服务器、内网工作站三台设备，希望使用外网笔记本通过云服务器转发，访问内网工作站；这里使用frp进行内网穿透。 云服务器端配置 登录腾讯轻量型云服务器控制台，开放转发端口、bind_port以及deshboad…
阅读更多...
CSDN等级权益概览

CSDN等级权益概览

文章目录 一、[权益概览](https://blog.csdn.net/SoftwareTeacher/article/details/114499372)二、权益详情（更新中...）2.1、等级权益2.2、原创保护2.3、推广管理2.4、博客皮肤 一、权益概览 级别对应分数解释权益未定级0这类用户没有做任何贡献。或者曾…
阅读更多...
EMG肌肉信号处理合集 (一）

EMG肌肉信号处理合集 (一）

本文归纳了常见的肌肉信号预处理流程，方便EMG信号的后续分析。使用pyemgpipeline库 来进行信号的处理。文中使用了 UC Irvine 数据库的下肢数据。 目录 1 使用wrappers 定义数据类，来进行后续的操作 2 肌电信号DC偏置去除 3 带通滤波器处理 4 对肌电…
阅读更多...
Windows安装Hadoop运行环境

Windows安装Hadoop运行环境

1、下载Hadoop 2、解压Hadoop tar zxvf hadoop-3.1.1.tar.gz3、设置Hadoop环境变量 3.1.1、系统环境变量 # HADOOP_HOME D:\software\hadoop-3.1.13.1.2、Path 环境变量 %HADOOP_HOME%\bin %HADOOP_HOME%\sbin3.1.3、修改Hadoop文件JAVA_HOME 注 : 路径中不要出现空格 ,…
阅读更多...
原理Redis-SkipList

原理Redis-SkipList

SkipList ZipList和QuickList的共同特点是节省内存。在遍历元素时，只能从头到尾或从尾到头，所以在查找头尾元素性能还是不错的，但是中间元素查询的性能就会差。 **SkipList（跳表）**首先是链表，但与传统链表…
阅读更多...
阿里云99元服务器ECS经济型e实例性能如何？测评来了

阿里云99元服务器ECS经济型e实例性能如何？测评来了

阿里云服务器优惠99元一年，配置为云服务器ECS经济型e实例，2核2G配置、3M固定带宽和40G ESSD Entry系统盘，CPU采用Intel Xeon Platinum架构处理器，2.5 GHz主频，3M带宽下载速度384KB/秒，上传速度1028KB/秒&am…
阅读更多...
链表OJ--上

链表OJ--上

文章目录 前言一、反转链表二、移除链表元素三、链表中倒数第K个结点四、相交链表五、链表的中间结点 前言 一、反转链表 力扣206：反转链表- - -点击此处传送 思路图： 方法一：改变指向 方法二： 代码： //方法一 /…
阅读更多...
BLE通用广播包

BLE通用广播包

文章目录 1、蓝牙广播数据格式2、扫描响应数据 1、蓝牙广播数据格式 蓝牙广播包的最大长度是37个字节，其中设备地址占用了6个字节，只有31个字节是可用的。这31个可用的字节又按照一定的格式来组织，被分割为n个AD Structure。如下图所示&…
阅读更多...
【11月比赛合集】48场可报名的数据挖掘大奖赛，任君挑选！

【11月比赛合集】48场可报名的数据挖掘大奖赛，任君挑选！

CompHub[1] 实时聚合多平台的数据类(Kaggle、天池…)和OJ类(Leetcode、牛客…）比赛。本账号会推送最新的比赛消息，欢迎关注！ 以下信息仅供参考，以比赛官网为准 目录 Kaggle（9场比赛）阿里天池（…
阅读更多...
Java计算时间差，距结束还有几天几小时几分钟

Java计算时间差，距结束还有几天几小时几分钟

文章目录 1、写法2、备份3、LocalDate、LocalDateTime、Date、String互转 1、写法 //静态方法，传入年月日时分秒 LocalDateTime startTime LocalDateTime.of(2023, 11, 22, 15, 09, 59); LocalDateTime endTime LocalDateTime.of(2023, 11, 30, 0, 0, 0); //计算…
阅读更多...
华清远见嵌入式学习——网络编程——作业4

华清远见嵌入式学习——网络编程——作业4

作业要求&#xff1a;①使用IO多路复用中的select函数实现TCP并发服务器客户端 ②使用IO多路复用中的poll函数实现TCP并发服务器的服务器端 一、 代码 #include <myhead.h>#define SERPORT 8888 //服务器端口号 #define SERIP "192.168.114.113"…
阅读更多...
PCIE链路训练-状态跳转1

PCIE链路训练-状态跳转1

A&#xff1a;12ms超时&#xff0c;或者再任何lane上检测到Electrical Idle Exit&#xff1b; B&#xff1a; 1.发送“receiver detection”之后没有一个lane的接收逻辑被rx检测到 2.不满足条件c&#xff0c;比如两次detection出现差别&#xff1b; C&#xff1a;发送端在没…
阅读更多...
数据分析基础之《matplotlib（1）—介绍》

数据分析基础之《matplotlib（1）—介绍》

一、什么是matplotlib 1、专门用于开发2D图表&#xff08;包括3D图表&#xff09; 2、使用起来及其简单 3、以渐进、交互方式实现数据可视化 4、matplotlib mat&#xff1a;matrix&#xff08;矩阵&#xff09; plot&#xff1a;画图 lib&#xff1a;库 二、为什么要学习m…
阅读更多...
万界星空科技SMT行业生产管理MES系统解决方案

万界星空科技SMT行业生产管理MES系统解决方案

一、SMT行业特点&#xff1a; SMT&#xff08;Surface Mounted Technology&#xff09;作为电子组装行业里首先的技术和工艺&#xff0c;选择合适的MES解决方案来保障SMT生产的成功至关重要。 电子行业涉及的范围非常广&#xff0c;包含了汽车、电脑、电视、手机等产品上&…
阅读更多...
SPASS-ARIMA模型

SPASS-ARIMA模型

基本概念 在预测中，对于平稳的时间序列，可用自回归移动平均（AutoRegres- sive Moving Average, ARMA）模型及特殊情况的自回归（AutoRegressive, AR）模型、移动平均（Moving Average, MA）模型等来拟合，预测该时间序列的未来值，但在实际的经济预测中，随机数据序列往往…
阅读更多...
【uni-app】uniapp中弹出输入框的示例

【uni-app】uniapp中弹出输入框的示例

uni.showModal({title: 请输入企业名称,content: ,editable: true, //是否显示输入框placeholderText: 请输入企业名称, //输入框提示内容confirmText: 确认,cancelText: 取消,success: (res) > {if (res.confirm) {this.checkDesc.name res.content;// console.log(输入的…
阅读更多...
使用Pytorch从零开始构建DCGAN

使用Pytorch从零开始构建DCGAN

在本文中&#xff0c;我们将深入研究生成建模的世界&#xff0c;并使用流行的 PyTorch 框架探索 DCGAN&#xff08;生成对抗网络 (GAN) 的一种变体&#xff09;的实现。具体来说&#xff0c;我们将使用 CelebA 数据集&#xff08;名人面部图像的集合&#xff09;来生成逼真的合…
阅读更多...
【技巧】PDF文件如何编辑？

【技巧】PDF文件如何编辑？

日常办公中我们经常会用到PDF文件&#xff0c;PDF具备很好的兼容性、稳定性及安全性&#xff0c;但却不容易编辑&#xff0c;那PDF要如何编辑呢&#xff1f; 如果打开PDF文件就只是只读的性质&#xff0c;说明文件是在线打开&#xff0c;或者通过PDF阅读器打开的&#xff0c;这…
阅读更多...
AIGC，ChatGPT AI绘画 Midjourney 注册流程详细步骤

AIGC，ChatGPT AI绘画 Midjourney 注册流程详细步骤

AI 绘画，Midjourney完成高清图片绘制，轻松掌握AI工具。 前期准备： ① 一个能使用的谷歌账号 ② 可以访问外网 Midjourney注册 1.进入midjourney官网https://www.midjourney.com 点击左下角”Join the Beta”，就可以注册，第一次使用的小伙伴会弹出提示，只需要点击Acc…
阅读更多...
如何有效解决UDP协议传输问题实现快速安全的文件传输

如何有效解决UDP协议传输问题实现快速安全的文件传输

随着互联网技术的不断发展&#xff0c;UDP协议作为一种快速、简单的传输协议被广泛应用于文件传输领域。然而&#xff0c;UDP协议传输过程中也存在着一些问题&#xff0c;如传输速度不稳定、数据丢失等&#xff0c;这些问题会影响到文件传输的效率和安全性。本文将介绍UDP协议传…
阅读更多...
最新文章

Copyright @ 2022~2023