622.设计循环队列(LeetCode)

思路

先确定什么情况为空,什么情况为满

这里有两种解决方案

1.留一个空间空置,当rear+1 == front时 ,则队列为满 (这里我们选用方案一)

2.增加一个size变量记录数据个数,size == 0则为空,size == k则为满

第一部分,确定为空的情况,我们规定:当front == rear时,队列为空(此时rear表示的是尾部元素的下一位,和栈中的top有异曲同工之妙)。

第二部分,确定为满的情况,当rear+1 == front时 ,则队列为满

实现一(用链表实现)

我们先来分析一下链表实现的场景,先给一个单向循环链表

push 1 2 3 4 5,此时达到了满的条件:rear->next == front 

pop 2次 ,front只用往后两个节点即可,并不用修改数据(因为后面继续push会覆盖)

 此时不满,又可以继续push 6 7,rear接着向后移动,并且插入新数据

 这样看起来,是不是链表实现还挺简单的?但是,这里有一个接口就很难受了——获取队尾数据

有没有解决方法呢?肯定有,只是比较麻烦。 有三种解决方案,第一种双向链表,第二种增加一个rearPrev指针,每次rear往后移时,rearPrev要记录前一个位置,第三种遍历获取队尾数据

那有人可能会说,我可以让rear指向队尾元素,那开头rear就必须指向NULL,又多出了对空指针的判断。所以牵一发而动全身,这里用链表实现可以,但比较麻烦。 

实现二 (用数组实现 )

那么链表实现比较麻烦,数组实现就简单吗?确实!这里用数组实现队列,代码会简洁不少,所以这里详细讲解用数组实现,有兴趣的小伙伴也可以去实现链表。

同样,先给一个空数组,满足front == rear的条件 

 push 1 2 3 4 5,此时rear+1 == front,达到满的条件。可是,rear+1 ==front是我们假想它是循环的,现实中应该怎么书写判满的条件呢?

假设循环队列存储k个有效数据,此时k == 5,开辟6个空间。  标出下标,那么此时我们可以利用取模,得出(rear+1)%(k+1)== front 的条件,其中k+1是空间个数,此时rear==5,+1为6,取模6,就变为0,就与front相等了(是不是很神奇?)

 

让我们再来看看其他情况 ,我们先pop 3次,让队列可以插入

 push 6 7 8 9,最后一个失败,此时又为满,再来分析一下:rear==2,+1为3,取模6,还是3,正好是front(是不是又验证了一遍我们的判断条件?)

分析了这么久,我们终于要开始写代码了。 

先创建MyCircularQueue结构体,并对其初始化 (这里就省略申请失败的条件,因为oj题基本不会申请失败),注意这里记得数组a开辟k+1个空间

和分析一样,先写出判空和判满的函数 ,有了前面的分析,这里是不是就很好理解了?

空:front == rear

满:(rear+1)%(k+1)==  front

 向循环队列插入数据,先判断队列是否为满,如果不满,在队尾rear插入数据,rear++(不过注意,rear有可能在边界,++要循环回来,所以最后%=(k+1));如果为满,则返回false,表示插入失败。

 从循环队列删除数据,同样也先判断队列是否为空,如果不空,则front++,再%=(k+1);如果为空,则表示删除失败,返回false

 获取队头元素,这个也超级简单。先判断是否为空,不为空,则直接返回下标为front的元素;如果为空,则返回-1

 获取队尾数据关键点来了。我们就是因为链表实现这个功能复杂,才选择了数组,让我们来看看数组是怎样实现这个功能的呢?一般情况,rear如果不在边界,我们就返回下标为rear-1的元素,如果rear刚好在最左边,那就返回下标为k的元素。这里可以用一个条件判断来写代码。

但是,有一种更妙的方法,先判断是否为空,不为空,则返回下标为(rear+k)%(k+1)的元素。这是什么意思呢?其实完整的写是(rear-1+k+1)%(k+1),相当于rear为0是,rear-1为-1,但是此时加上k+1,再取模k+1,就变成了k。(是不是很妙?) 

 最后,就是简单的释放空间,先释放数组空间,再释放队列空间。

完整代码附上:




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


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

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

    return obj;
}

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

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

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

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

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

int myCircularQueueRear(MyCircularQueue* obj) {
    if (!myCircularQueueIsEmpty(obj))
    {
        return obj->a[(obj->rear+obj->k)%(obj->k+1)];
    }
    return -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/151069.html

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

相关文章

Uniapp导出的iOS应用上架详解

​ 目录 Uniapp导出的iOS应用上架详解 摘要 引言 苹果审核标准 苹果调试 注意事项和建议 总结 摘要 本文将探讨Uniapp导出的iOS应用能否成功上架的问题。我们将从苹果审核标准、性能影响、调试流程等多个方面进行深入分析,以及向开发者提供相关注意事项和建…

【计算机网络笔记】DHCP协议

系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…

JAVA 中集合取交集

日常工作 经常需要取两个数据集的交集。对常用的List 和Set集合做了一个测试 public static void main(String[] args) {List<Integer> list1 Lists.newArrayList();List<Integer> list2 Lists.newArrayList();Set<Integer> set3 Sets.newHashSet();Set&l…

优秀智慧园区案例 - 重庆AI PARK智慧创意园区,先进智慧园区建设方案经验

一、项目背景 1、智慧园区是国家实现经济增长、产业升级的载体 智慧园区建设是城市智慧化创新发展的核心&#xff0c;在数智化升级和低碳化转型的经济发展双引擎的驱动下&#xff0c;十四五、数字经济的政策大力支持&#xff0c;以及人工智能、5G、大数据、区块链等技术的不断…

ubuntu中cuda12.1配置(之前存在11.1版本的cuda)(同时配置两个版本)

ubuntu中cuda12.1配置 由于YOLOv8项目中Pytorch版本需要cuda12.1版本 在官网下载12.1版本的deb包 官网地址 sudo dpkg -i cuda-keyring_1.0-1_all.deb sudo apt-get update sudo apt-get -y install cuda然后需要修改bashrc文件&#xff08;隐藏文件&#xff09; 添加 exp…

Postman实现接口的加密和解密

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 1、目前市面上的加密的方式 对称式加密&#xff1a;DES&#xff0c;AES&#xff0c;Base64加密算法 非对称加密&#xff1a…

基于STC12C5A60S2系列1T 8051单片机的数模芯片TLC5615实现数模转换应用

基于STC12C5A60S2系列1T 8051单片的数模芯片TLC5615实现数模转换应用 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍数模芯片TLC5615介绍通过按键调节数模芯片TLC5615…

Postman的Cookie鉴权

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 一&#xff09;什么是Cookie 定义&#xff1a;存储在客户端的一小段文本信息&#xff0c;格式为键值对的形式. 二&#xff09…

低代码编辑平台后台实现

背景 之前做过一个前端低代码编辑平台&#xff0c;可以实现简单的移动端页面组件拖拽编辑&#xff1a; https://github.com/li-car-fei/react-visual-design 最近基于C的oatpp框架实现了一下后台。使用oatpp框架做web后台开发时&#xff0c;发现按照官方的示例使用的话&#…

氢原子波函数等概率面的绘制

氢原子波函数等概率面的绘制 归一化后的氢原子波函数

高浓度白酒废水处理需要哪些设备

高浓度白酒废水处理需要的设备包括预处理设备、生物反应器、二级处理设备、消毒装置等。 预处理设备&#xff1a;包括格栅、筛网等&#xff0c;用于去除污水中的大颗粒物和杂质。生物反应器&#xff1a;用于进行生物反应&#xff0c;去除污水中的有机物和氨氮等污染物。二级处…

基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码

基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于平衡优化器算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于平衡优化器优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要&#xff1a;针…

Linux 系统编程,Binder 学习,文件访问相关的接口

文章目录 Linux 系统编程&#xff0c;Binder 学习&#xff0c;文件访问相关的接口1.概念2.linux文件结构3.文件描述符4.Linux文件系统的两类常用接口&#xff0c;linux系统内置库函数4.1 open4.2 close4.3 read4.4 write 5.标准I/O库函数5.1 fopen Linux 系统编程&#xff0c;B…

IDEA 高分辨率卡顿优化

VM设置优化 -Dsun.java2d.uiScale.enabledfalse 增加该条设置&#xff0c;关闭高分切换 https://intellij-support.jetbrains.com/hc/en-us/articles/115001260010-Troubleshooting-IDE-scaling-DPI-issues-on-Windows​intellij-support.jetbrains.com/hc/en-us/articles/1…

c语言判断链表是否为循环链表

普通链表与循环链表的区别在于&#xff1a;普通链表的最后一个节点指向为NULL&#xff0c;而循环链表最后一个节点指向该链表中的任意一个节点&#xff0c;如同一个环。循环链表问题引出了一个在链表中很重要的概念&#xff1a;快、慢指针。快、慢指针可以帮助我们解决很多经典…

使用jmeter+ant进行接口自动化测试(数据驱动)

本次接着介绍如何利用apache-ant执行测试用例并生成HTML格式测试报告 ①下载安装 apache-ant-1.9.9&#xff0c;配置环境变量 如下方式检验安装成功 ②安装好ant后&#xff0c;把jmeter中extras目录下的ant-jmeter-1.1.1.jar 文件copy到ant安装目录下的lib文件夹中 ③配置ant…

ssm045基于jsp的精品酒销售管理系统+jsp

ssm045基于jsp的精品酒销售管理系统jsp 交流学习&#xff1a; 更多项目&#xff1a; 全网最全的Java成品项目列表 https://docs.qq.com/doc/DUXdsVlhIdVlsemdX 演示 项目功能演示&#xff1a; ————————————————

247:vue+openlayers 根据坐标显示多边形(3857投影),计算出最大幅宽

第247个 点击查看专栏目录 本示例是演示如何在vue+openlayers项目中根据坐标显示多边形(3857投影),计算出最大幅宽。这里先通过Polygon来显示出多边形,利用getExtent() 获取3857坐标下的最大最小x,y值,通过ransformExtent转换坐标为4326, 通过turf的turf.distance和计算…

Vue3清除Echarts图表

一&#xff1a;前言 Vue3是一款流行的JavaScript框架。它提供了丰富的工具和组件&#xff0c;使得开发者可以轻松构建交互式的Web应用程序。而Echarts是一款功能强大的图表库&#xff0c;它可以帮助开发者以直观的方式展示数据。 在使用Vue3和E charts的过程中&#xf…

【数电】IEEE754浮点数

IEEE754浮点数 1.组成及分类2.计算(1)符号位(2)阶码(3)尾码(4)实际计算公式 1.组成及分类 &#xff08;1&#xff09;组成 IEEE754浮点数由三部分组成&#xff1a;符号位、阶码和尾码。 &#xff08;2&#xff09;分类 根据数据位宽分为三类&#xff1a;短浮点数、长浮点数和…