手把手设计C语言版循环队列(力扣622:设计循环队列)

文章目录
- 前言
- 描述
- 分析
- 力扣AC代码
力扣: 622.设计循环队列
前言
队列会出现“假溢出”现象,即队列的空间有限,队列是在头和尾进行操作的,当元素个数已经达到最大个数时,队尾已经在空间的最后面了,但是对头前面的不一定是满的。针对这一现象,引入了循环队列。循环队列也是一种数据结构,小编在本篇文章中,是以力扣的一道题目为例来设计循环队列。
此时队尾rear已经到最后面了,但是队头front前面没有填满元素,因此并没有满

循环队列就是将队尾rear再次回到数组的前面,解决“假溢出”的现象

继续在队尾rear插入元素,直到真的满了

描述
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
你的实现应该支持如下操作:
- MyCircularQueue(k): 构造器,设置队列长度为 k 。
- Front: 从队首获取元素。如果队列为空,返回 -1 。
- Rear: 获取队尾元素。如果队列为空,返回 -1 。
- enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
- deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
- isEmpty(): 检查循环队列是否为空。
- isFull(): 检查循环队列是否已满。
示例:
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
分析
在普通的队列中,队满的条件是rear==front,那么在循环队列中怎么判断队列已经满了?
常用的一个解决方法是,多开一个空间。也就是说,当队列满的时候,还是有一个空间没有被使用。

rear可能比front大,也可能比front所以尽管它们只相差一个位置时就是满的情,但也可能是相差整整一圈,所以若队列长度为k,那么需要多开辟一个空间,即k+1。因此,队满的额条件为(rear+1)%(k+1)==front。取模“%”的目的就是为了整合front和rear大小的问题,解决多绕了一圈的问题。
什么时候队列为空呢?
rear==front时队列为空。
总结一下就是:
- 当
rear==front时队列为空; - 当
rear的下一个和front相等,则队列满
分析完队满、对空问题,回到本道题目就很好解决了。
构造器:
MyCircularQueue* obj是一个结构体指针,需要给obj开辟一个空间,其次开辟一个数组a,初始化front 和 back 以及k
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int *)malloc((k+1)*sizeof(int));obj->front=0;obj->back=0;obj->k=k;return obj;
}
判断队空、队满:
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->back;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1)%(obj->k+1)==obj->front;
}
队尾插入:
首先需要判断队列是否已经满了,如果满了返回false,如果没有,执行插入操作。先插入,再将队尾obj->back++。
需要注意的是,这里是一个循环队列,如果此时已经在最后一个单元里面插入元素,那么obj->back应该是回到前面,而不是继续往后。此时有需要用到取模“%”操作,使得 obj->back=(obj->back)%(obj->k+1)

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj->back++;obj->back=(obj->back)%(obj->k+1);return true;
}
队头删除:
删除只需要将obj->front++即可
但是依然需要注意,这是一个循环队列,当obj-front在最后一片单元时,需要回到前面,obj->front=(obj->front)%(obj->k+1)
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;obj->front=(obj->front)%(obj->k+1);return true;
}
取队头元素:
先判断队列是否为空,不为空执行取队头操作
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}
取队尾元素:
首先判断队列是否为空,不为空执行取队尾元素操作
需要注意的是,当obj->back==0时,此时取得应该是最后一个存储单元的元素,这里需要单独判断一下,其余的情况都是obj->back 前面一个单元的元素。
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}else if(obj->back==0){return obj->a[obj->k];}else{return obj->a[obj->back-1];}
}
销毁:
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}
力扣AC代码
typedef struct {int *a;int front;int back;int k;} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a=(int *)malloc((k+1)*sizeof(int));obj->front=0;obj->back=0;obj->k=k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front==obj->back;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back+1)%(obj->k+1)==obj->front;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->a[obj->back]=value;obj->back++;obj->back=(obj->back)%(obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->front++;obj->front=(obj->front)%(obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;return obj->a[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}// return obj->a[(obj->back+obj->k)%obj->k+1];else if(obj->back==0){return obj->a[obj->k];}else{return obj->a[obj->back-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);
*/

相关文章:
手把手设计C语言版循环队列(力扣622:设计循环队列)
文章目录 前言描述分析力扣AC代码 力扣: 622.设计循环队列 前言 队列会出现“假溢出”现象,即队列的空间有限,队列是在头和尾进行操作的,当元素个数已经达到最大个数时,队尾已经在空间的最后面了,但是对头…...
数据仓库及ETL的理论基础
数据仓库(Data Warehouse)是一个用于存储和管理大量结构化数据的系统,旨在支持企业的决策制定过程。它是一个集成的、主题导向的、时间变化的、非易失性的数据集合,用于支持企业的决策制定过程。数据仓库的设计目标是提供高性能的…...
5-4计算一串字符的空格数字字符其他
#include<stdio.h> int main(){char c;int space0;//空格int letters0;//英文字母int numbers0;//数字int others0;//其他字符printf("请输入一行字符:");while((cgetchar())!\n)//获取字符的内容,到\n停止{if(c>a&&c<z|…...
leetcode面试经典150题——30 长度最小的子数组
题目:长度最小的子数组 描述: 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组&a…...
学习计划计划执行记录
11.21--写下学习目标 游戏行业通识学习: 求知鱼游戏学院的个人空间-求知鱼游戏学院个人主页-哔哩哔哩视频 (bilibili.com) (28 封私信 / 80 条消息) 游鲨游戏圈 - 知乎 (zhihu.com) 书籍学习: 软技能2:软件开发者职业生涯指南 面经学习…...
【紫光同创PCIE教程】——使用WinDriver驱动紫光PCIE
本原创教程由深圳市小眼睛科技有限公司创作,版权归本公司所有,如需转载,需授权并注www.meyesemi.com) 紫光的logos系列的PGL50H/PGL100H、logos-2全系列都集成gen24的PCIE硬核,且官方也提供了例程。 紫光的PCIE用起来还是挺方便的…...
MT8735/MTK8735安卓核心板规格参数介绍
MT8735核心板是一款高性能的64位Cortex-A53四核处理器,设计用于在4G智能设备上运行安卓操作系统。这款多功能核心板支持LTE-FDD/LTE-TDD/WCDMA/TD-SCDMA/EVDO/CDMA/GSM等多种网络标准,同时还具备WiFi 802.11a/b/g/n和BT4.0LE等无线通信功能。此外&#x…...
NSSCTF web刷题记录6
文章目录 [HZNUCTF 2023 final]eznode[MoeCTF 2021]地狱通讯-改[红明谷CTF 2022] Smarty Calculator方法一 CVE-2021-26120方法二 CVE-2021-29454方法三 写马蚁剑连接 [HZNUCTF 2023 final]eznode 考点:vm2沙箱逃逸、原型链污染 打开题目,提示找找源码 …...
米哈游大数据云原生实践
云布道师 近年来,容器、微服务、Kubernetes 等各项云原生技术的日渐成熟,越来越多的公司开始选择拥抱云原生,并将企业应用部署运行在云原生之上。随着米哈游业务的高速发展,大数据离线数据存储量和计算任务量增长迅速,…...
移动端适配-(postcss-pxtorem)
基于vuevant的移动端适配(rem) 1.下载lib-flexible --save npm i lib-flexible --save2.在main.js中引入lib-flexible main.js import lib-flexible/flexible3.设置meta标签 <meta name"viewport" content"widthdevice-width, initial-scale1, maximum-s…...
【PostgreSQL】解决PostgreSQL时区(TimeZone)问题
问题描述 最近在使用PostgreSQL中,对行记录进行设置创建时间(created_time)时,出现了设置了now()时间而数据库中写入的数据是不一致的数据。 eg: insert into dept ( created_at, updated_at) VALUES (now(),now())…...
Vue Router的使用
Vue.js是一个流行的JavaScript框架,用于开发单页面应用程序。Vue提供了一个强大的路由系统,可以帮助我们管理应用程序中的不同页面。在本文中,我们将详细讲解Vue路由的使用方法。 目录 1. 安装Vue Router2. 创建路由实例3. 配置路由4. 在模板…...
海外IP代理科普——API代理
随着互联网的不断发展,越来越多的企业开始使用API(应用程序接口)来实现数据的共享和交流。而在API使用中,海外代理IP也逐渐普及。那么,什么是API代理IP呢?它有什么作用?API接口有何用处…...
详解Python安装requests库的实例代码
文章目录 前言基本用法基本的get请求带参数的GET请求解析json关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Python工具包项目源码合集①Python工具包②Python实战案例③Python小游戏源码五、面试资料六、Python兼职渠道 前…...
Flutter 使用 device_info_plus 遇到的问题
问题:引用device_info_plus 插件出现了异常,不知道为啥打开项目的时候就不能用了。 解决:改了版本解决 Target of URI doesnt exist: package:device_info_plus/device_info_plus.dart. (Documentation) Try creating the file reference…...
论文阅读:“基于特征检测与深度特征描述的点云粗对齐算法”
文章目录 摘要简介相关工作粗对齐传统的粗对齐算法基于深度学习的粗对齐算法 特征检测及描述符构建 本文算法ISS 特征检测RANSAC 算法3DMatch 算法 实验结果参考文献 摘要 点云对齐是点云数据处理的重要步骤之一,粗对齐则是其中的难点。近年来,基于深度…...
[python]python筛选excel表格信息并保存到另一个excel
目录 关键词平台说明背景所需库1.安装相关库2.代码实现sourcetarget1 关键词 python、excel、DBC、openpyxl 平台说明 项目Valuepython版本3.6 背景 从一个excel表中遍历删选信息并保存到另一个excel表 所需库 1.openpyxl :是一个用于读写 Excel 文件的 Pyt…...
使用kafka_exporter监控Kafka
prometheus 监控 kafka 常见的有两种开源方案,一种是传统的部署 exporter 的方式,一种是通过 jmx 配置监控, 项目地址: kafka_exporter:https://github.com/danielqsj/kafka_exporterjmx_exporter:https://github.com/prometheus/jmx_exporter本文将采用kafka_exporter方…...
基于Bagging集成学习方法的情绪分类预测模型研究(文末送书)
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
Java算法(八)手写String集合元素去重的两种实现方式 正序 逆序 删除集合中符合条件的字符串
Java算法(八): 实现集合去重 需求:创建一个存储String的集合,内部存储(test, 张三, test,test, 李四)字符串 删除所有的test字符串,删除后&#…...
别被代理忽悠了!程序员视角下的专利技术交底书避坑指南(附真实案例)
技术人必备的专利交底书实战手册:从核心创新到授权落地的全流程解析 当你在深夜调试代码时灵光一现的算法优化,或是为了解决某个技术瓶颈而设计的独特架构方案,这些都可能成为改变行业游戏规则的技术专利。但现实情况是,超过60%的…...
科学拉丁文献翻译评测:ChatGPT与Google Translate的深度对比
1. 项目缘起与核心价值作为一名长期在生物、医药和古典文献领域打交道的从业者,我几乎每天都要和拉丁文打交道。无论是解读一份18世纪的植物志手稿,还是理解一篇现代药理学论文中引用的经典术语,拉丁语都是横亘在面前的一道坎。过去ÿ…...
CANN/opbase获取Tensor格式
aclGetFormat 【免费下载链接】opbase 本项目是CANN算子库的基础框架库,为算子提供公共依赖文件和基础调度能力。 项目地址: https://gitcode.com/cann/opbase 功能说明 获取aclTensor的format,aclTensor由aclCreateTensor接口创建。 函数原型 …...
Blender骨骼次级动画插件WiggleBone:原理、参数与实战指南
1. 项目概述与核心价值如果你在寻找一个能让你在3D建模或游戏开发中,为骨骼动画添加“灵魂”的工具,那么detomon/wigglebone这个项目绝对值得你花时间深入研究。简单来说,它是一个为 Blender 设计的插件,专门用来模拟骨骼的次级动…...
如何高效实现小说资源自动化采集:Rust开源方案深度解析
如何高效实现小说资源自动化采集:Rust开源方案深度解析 【免费下载链接】Tomato-Novel-Downloader 番茄小说下载器不精简版 项目地址: https://gitcode.com/gh_mirrors/to/Tomato-Novel-Downloader 番茄小说下载器(Tomato-Novel-Downloader&#…...
安防/车载项目实战:用RK3588+NVP6188搞定AHD摄像头接入(附完整DTS配置与避坑点)
RK3588NVP6188工业级AHD摄像头接入实战:从硬件设计到多路预览的完整指南 在智能安防和车载电子领域,高清视频采集系统的稳定性直接决定了整个项目的成败。传统MIPI摄像头虽然画质出色,但传输距离的限制让它在停车场监控、行车记录仪等需要长距…...
基于MCP协议为Claude Code构建跨运行时记忆共享系统
1. 项目概述:为Claude Code构建一个无损的跨运行时记忆层如果你和我一样,是Claude Code的重度用户,同时又在使用OpenClaw生态下的各种AI助手(比如Daphne、JelleeBean),那么你一定遇到过这样的困扰ÿ…...
深入V4L2内核:当DQBUF卡在wait_event时,我们该如何调试与自救?
深入V4L2内核:当DQBUF卡在wait_event时的调试与解决方案 在Linux视频开发领域,V4L2框架是连接用户空间和摄像头驱动的核心桥梁。然而,当用户态应用调用VIDIOC_DQBUF时,有时会遇到进程永久阻塞的情况,特别是在设备异常状…...
TensorFlow文本分类实战:从原理到部署
1. 文本分类与神经网络的核心价值文本分类是自然语言处理(NLP)中最基础也最实用的技术之一。想象一下每天处理的邮件自动归类、电商平台的商品评论分析、社交媒体的内容审核——这些场景背后都离不开高效的文本分类系统。传统方法依赖人工设计特征和规则…...
Pixel Epic · Wisdom Terminal 网络问题诊断助手:智能化排查403 Forbidden等常见错误
Pixel Epic Wisdom Terminal 网络问题诊断助手:智能化排查403 Forbidden等常见错误 1. 当开发者遇到403错误时 想象一下这样的场景:凌晨两点,你正在赶一个重要的项目上线,突然发现应用返回403 Forbidden错误。服务器日志没有明…...
