leetcode经典例题之环形队列

P. S.:以下代码均在VS2019环境下测试,不代表所有编译器均可通过。
P. S.:测试代码均未展示头文件stdio.h的声明,使用时请自行添加。

  

目录

  • 1、题目展示
  • 2、问题分析
  • 3、完整代码展示
  • 4、结语

1、题目展示

在这里插入图片描述


  在拿到题目时,通过分析我们知道,环形队列是一个有用固定位置数的队列,若队列已满就不能再向其中插入数据,且队列为循环,及队列的尾部的下一个为队列的头部。
  在这种前提条件下,我们会联想到可以使用链表的形式进行实现,但是在使用链表创建队列时,需要开辟出题目要求数量的节点,并将其连接起来,十分麻烦,且在进行删除插入操作时会有对指针的操作,容易出现bug,故本文仅对如何使用数组来实现循环队列进行讲解。


2、问题分析


  当使用数组来实现队列时,我们可以先假设题目要求创建四个空间存储空间的循环队列,示意图如下:

在这里插入图片描述  在创建好数组之后我们又如何让其可以循环呢,可以思考,当指向下标的位置越过了数组限制下标3时,我们让他取模,并回归到数组的0下标,或者也可以设置一个size来记录数组内数据的个数,并通过size来进行循环。


  可循环的问题解决了,那我们如何判断循环队列中的空间是否满了或者空呢,我们可以设置两个数分别为head和tail,让其指向数组的首元素下标,即开始时head和tail都为0,当head和tail相等时,就判断它时空的循环队列。
  可这时问题又出现了,当我们队列里存满了数据时,head也和tail相等,这就造成了很明显的bug,无法判断是相等还是空,这时我们可以在创建数组时多创建一个空间,比如说我们需要四个空间,在创建时就创建五个空间,但是数组里最多只存储四个数据,即总有一个空间是不存储数据的,这样就完美的解决了假溢出的问题。示意图如下:

在这里插入图片描述

  此时我们假设进行两步操作,第一次向循环队列中插入四个数据,第二次删除四个数据。示意图分别如下:
在这里插入图片描述
在这里插入图片描述


  我们可以明显地发现当tail的下一个位置为head时,循环队列时满的状态,当tail等于head时,循环队列是空的状态。
  至此我们便可以依据此种规律进行代码的书写。


3、完整代码展示


  至于如何对越界的head和tail进行取模转换,是一个数学上的问题,再此不再做过多的详解,看官可通过数学知识自行解答,下面是完整代码展示:
typedef struct 
{
    int* a;
    int head;
    int tail;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->a = (int*)malloc(sizeof(int)*(k+1));
    obj->head = 0;
    obj->tail = 0;
    obj->k = k;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    return obj->head == obj->tail;
}

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

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

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

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

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


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




4、结语


  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
  如需引用,注明地址。

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

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

相关文章

前端动态旋转地球背景

效果图 贴下源码 <template><div class"map-bg"><div class"canvas" id"canvs"></div><canvas class"canvasxk" id"canv"></canvas></div> </template><script setup …

如何快速提取出一个文件里面全部指定类型的文件的全部路径

首先&#xff0c;需要用到的这个工具&#xff1a; 度娘网盘 提取码&#xff1a;qwu2 蓝奏云 提取码&#xff1a;2r1z 打开工具&#xff0c;切换到第五个模块&#xff0c;文件批量复制模块&#xff08;快捷键&#xff1a;Ctrl5&#xff09; 点击右边的“搜索添加”按钮&#…

20 分页:较小的表

目录 简单的解决方案&#xff1a;更大的页 混合方法&#xff1a;分页和分段 多级页表 详细的多级示例 超过两级 ​编辑地址转换过程&#xff1a;记住TLB 反向页表 将页表交换到磁盘 之前提到的一个问题&#xff1a;就是页表太大&#xff0c;假设一个 32 位地址空间&…

高中数学:平面向量-基本概念

一、定义 有方向&#xff0c;且有大小的量&#xff0c;就叫向量 与之对应的是&#xff0c;数量&#xff0c;只有大小&#xff0c;没有方向 例如 A B → \mathop{AB}\limits ^{\rightarrow} AB→ a → \mathop{a}\limits ^{\rightarrow} a→ 二、相关性质 相等 大小相同…

(超详细讲解)实现将idea的java程序打包成exe (新版,可以在没有java的电脑下运行,即可以发给好朋友一起玩)

目录 实现打包到exe大概步骤 工具准备 1.将java程序文件打包成jar文件 2.准备好jre文件 3.使用exe4j软件打包好 4.最终打包 实现打包到exe大概步骤 1.打包需要满足的条件&#xff1a;将java文件转成jar文件的工具exe4j、 以及需要满足jdk1.8以上&#xff08;因安装exe4…

【必看】Spring系列面试题

Spring Core Container, AOP, Data Access, Web... 基础 1. 简单介绍Spring 一款开源的轻量级 Java 开发框架&#xff0c;旨在提高开发人员的开发效率以及系统的可维护性。Spring 支持 IoC&#xff08;Inversion of Control:控制反转&#xff09; 和 AOP(Aspect-Oriented Pro…

网络隔离状态下,如何可以安全高效地进行研发文件外发?

研发部门的数据传输通常需要保证数据的安全性、完整性和保密性&#xff0c;尤其是当涉及到公司的核心技术、产品设计、源代码等重要信息时。研发文件外发&#xff0c;即研发资料的外部传输&#xff0c;通常涉及到公司的核心技术和商业机密&#xff0c;因此需要采取严格的安全措…

动态NAT

在上一章静态NAT中我们提过了&#xff0c;静态NAT只能一对一映射&#xff0c;无法有效缓解IPV4地址池紧张的问题&#xff0c;那么我们今天来学习一个新的技术——动态NAT&#xff0c;来解决这个问题。 第一章 1.1 动态NAT工作流程 动态NAT基于地址池来实现私有地址和公有地址的…

学习软考----数据库系统工程师29

数据操作 SELECT基本结构 简单查询 连接查询 子查询 聚集函数 分组查询 字符串操作 集合操作 外连接 INSERT INTO语句 DELETE语句 UPDATE语句

融入新科技的SLM27211系列 120V, 3A/4.5A高低边高频门极驱动器兼容UCC27284,MAX15013A

SLM27211是高低边高频门极驱动器&#xff0c;集成了120V的自举二极管&#xff0c;支持高频大电流的输出&#xff0c;可在8V~17V的宽电压范围内驱动MOSFET&#xff0c;独立的高、低边驱动以方便控制&#xff0c;可用于半桥、全桥、双管正激和有源钳位正激等拓。有极好的开通、关…

下载文件名称乱码或变成了随机码

如图 后端是有正常返回附件名称的,浏览器开发工具中也正常显示了这个数据,但是下载下来的文件名称确实一堆随机码. 其实这个问题的原因是因为跨域 查看console: Refused to get unsafe header "content-disposition" 现象,后端传递到前端的fileName不能被识别,下载…

吴恩达2022机器学习专项课程C2(高级学习算法)W1(神经网络):Lab02 TensorFlow构建神经网络

这里写目录标题 实验目的导入训练集并绘制散点图特征缩放处理数据集扩展数据集TensorFlow构建神经网络模型1.设置模型的层2.获取模型信息2.优化模型3.设置模型参数3.开始预测4.转换预测结果 检测神经元的功能1.目的2.准备工作3.第一层的预测与真实数据的对比2.第二层3.神经网络…

【.net core】微信支付基础功能(开发及使用)

注意 微信开发前期准备工作参照&#xff1a;【微信开发】微信支付前期准备工作&#xff08;申请及配置&#xff09;-CSDN博客 本文仅提供微信支付下单&#xff0c;付款&#xff0c;回调&#xff0c;退款等基础功能内容&#xff0c;更多微信支付功能请参照微信支付官网:微信支…

GT2712-STBD 三菱触摸屏12.1寸型

GT2712-STBD 三菱触摸屏12.1寸型 GT2712-STBD参数说明&#xff1a;12.1型, SVGA, TFT彩色液晶屏 65536色, 黑色边框, 电源DC24V。 一、三菱触摸屏GT2712-STBD性能规格&#xff1a; [显示部*1*2] . 显示软元件:TFT彩色液晶屏 . GT2712-STBD画面尺寸:12.1寸 . GT2712-STBD…

这三大场景是未来电瓶车充电桩布局的重中之重

电瓶车充电桩主板作为电瓶车充电系统中的核心组成部分&#xff0c;在实际应用场景中发挥着关键作用。 电瓶车充电桩主板作为电瓶车充电系统的核心组成部分&#xff0c;在各种应用场景中发挥着关键作用。下面我们将一起探讨电瓶车充电桩主板未来重点布局的场景。 01、老旧小区—…

PVFS: A Parallel File System for Linux Clusters——论文泛读

ALS 2000 Paper 分布式元数据论文阅读笔记整理 问题 Linux集群作为低成本、高性能并行计算平台&#xff0c;但缺乏并行文件系统的支持&#xff0c;它对于此类集群上的高性能I/O至关重要。 本文方法 本文为Linux集群开发了一个并行文件系统&#xff0c;称为并行虚拟文件系统…

云原生技术发展概述:投身云计算,从拥抱云原生开始

一、云原生的起源 云计算领域正在进行着一场革命&#xff0c;主机虚拟化实现了主机资源的池化&#xff0c;可以看作是云计算的上半场。以容器为基础的云原生真正实现了应用层的弹性&#xff0c;可以看作是云计算的下半场。 图来源&#xff1a;CNCF公开资料 有人说&#xff0c…

AI+文旅|当智慧遇见风景,感受文旅新体验

今年的五一假期,公众出游热度持续升温&#xff0c;全国多地景区再现“人山人海”&#xff0c;在这样的背景下&#xff0c;促使文旅行业不断通过数字化手段&#xff0c;提升旅游体验质量、探索新的服务方式&#xff0c;AI技术的加入为旅游业带来了革命性的变化。智能导游、智能推…

nuxt3.0+scrollreveal动画插件实现页面滚动加载动画效果

项目安装 npm install scrollreveal --save 在src下创建plugins文件夹&#xff0c;写入名为scrollreveal.client.ts的文件。 import { defineNuxtPlugin } from "#app"; import scrollReveal from scrollrevealexport default defineNuxtPlugin((nuxtApp) > {l…

最新微信智能电子名片源码 全开源可二开 智能名片系统开发

在数字化日益深入人心的今天&#xff0c;名片已不再是简单的纸质交换工具&#xff0c;而是成为了一个展示个人或企业形象、促进商务交流的重要窗口。分享一款全新的微信智能电子名片系统&#xff0c;源码开源、可二次开发的灵活性&#xff0c;更在功能上进行了全面升级和优化&a…