设计循环队列——oj题622
.
专栏:LeetCode刷题|数据结构|Linux
路漫漫其修远兮,吾将上下而求索
文章目录
- 题目要求:
- 应该支持如下操作:
- 示例:
- 提示:
- 结构体定义
- 队列的创建
- 基本操作
- 判断队列是否为空:
- 判断队列是否已满:
- 入队操作:
- 出队操作:
- 获取队首和队尾元素:
- 内存释放
- 难点解释
- 难点1
- 难点2
- 难点3
要做题目的点击这里–>队列oj题——622.设计循环队列
题目要求:
设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 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
提示:
所有的值都在 0 至 1000 的范围内;
操作数将在 1 至 1000 的范围内;
请不要使用内置的队列库。
结构体定义
首先,我们定义一个名为 MyCircularQueue
的结构体来表示循环队列:
typedef struct {int *a; // 队列中的元素数组int k; // 队列的最大容量int front; // 指向队列头部元素的指针int back; // 指向队列尾部的下一个位置的指针
} MyCircularQueue;
在这个结构体中,a 是一个整型数组,用来存储队列中的元素。k 表示队列的最大容量,front 和 back 分别表示队列头部和尾部的指针。
队列的创建
队列的创建涉及到内存的分配和初始化:
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int *)malloc(sizeof(int)*(k+1));obj->front = obj->back = 0;obj->k = k;return obj;
}
这里,我们为队列结构体和队列数组分配内存。注意,我们为数组分配 k+1 的空间,因为在循环队列中,我们总是保留一个位置不使用,以区分队列为空和队列为满的状态。
基本操作
判断队列是否为空:
// 检查队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->front == obj->back; // 如果 front 和 back 相等,则队列为空
}
当 front
和 back
相等时,队列为空。
判断队列是否已满:
// 检查队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->back + 1) % (obj->k + 1) == obj->front; // 如果 back 的下一个位置是 front,则队列已满
}
如果 back
的下一个位置是 front
,则队列已满。
入队操作:
// 向队列中添加元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) // 如果队列已满,则无法添加元素return false;obj->a[obj->back] = value; // 在 back 的位置插入元素obj->back = (obj->back + 1) % (obj->k + 1); // 更新 back 的位置
在入队时,我们首先检查队列是否已满。如果不满,将元素放在 back
指向的位置,并更新 back
指针。
出队操作:
// 从队列中删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,则无法删除元素return false;obj->front = (obj->front + 1) % (obj->k + 1); // 更新 front 的位置return true;
}
出队时,我们检查队列是否为空。如果不为空,则移动 front 指针。
获取队首和队尾元素:
// 获取队列头部的元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1return -1;return obj->a[obj->front]; // 返回队列头部的元素
}// 获取队列尾部的元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj)) // 如果队列为空,返回 -1return -1;return obj->a[(obj->back - 1 + obj->k + 1) % (obj->k + 1)]; // 返回队列尾部的元素
}
这两个函数用于获取队首和队尾的元素。注意在获取队尾元素时,我们使用了模运算来正确处理环形结构。
内存释放
最后,当队列不再需要时,我们应该释放其占用的内存:
// 释放队列占用的内存
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a); // 释放数组内存free(obj); // 释放队列结构体内存
}
难点解释
难点1
这里我优化了代码,没有优化前是这样的:
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj)) // 如果队列已满,则无法添加元素return false;obj->a[obj->back] = value; // 在 back 的位置插入元素obj->back++; // 更新 back 的位置obj->back %=(obj->k+1);//确保值在循环队列的有效范围内return true;
}
难点2
1.循环队列的容量:在这个循环队列的实现中,队列的实际容量是
k + 1
,但为了区分空队列和满队列的状态,我们总是保留一个元素的空间不使用。所以,队列中最多可以存储k
个元素。
2.队列尾部指针
(obj->back)
:这个指针指向队列中下一个元素将要存放的位置。当一个新元素被加入队列时,它被放置在 obj->back 指向的位置,然后 obj->back 会向前移动一个位置。
3.队列头部指针
(obj->front)
:这个指针指向队列中当前的第一个元素。当一个元素被移出队列时,obj->front 会向前移动一个位置。
4.判断队列是否已满:
(obj->back + 1) % (obj->k + 1)
计算出obj->back
向前移动一个位置后的值,并使用模运算确保这个值在循环队列的有效范围内(即从 0 到 k)。
难点3
下面是这个表达式的详细解释:
1.
obj->back
: 指向队列中下一个插入元素的位置。
2.
obj->back - 1
: 因为 obj->back 指向的是下一个空位,所以队尾元素实际上是在 obj->back - 1 的位置。
3.由于队列是循环的,当
obj->back
为 0 时,obj->back - 1
会变成一个负数。为了正确地处理这种情况,我们加上 obj->k + 1,这保证了我们总是在一个正数的范围内操作。
4.
(obj->back - 1 + obj->k + 1) % (obj->k + 1)
: 这个模运算确保了即使加上了obj->k + 1
,结果仍然是在队列大小的合法范围内。因此,这个表达式能够正确地处理循环队列的尾部元素访问,无论obj->back
是在队列的开始位置还是任何其他位置
可以来我的github参观参观,看完整代码
路径点击这里–>oj622-设计循环队列
相关文章:
设计循环队列——oj题622
. 个人主页:晓风飞 专栏:LeetCode刷题|数据结构|Linux 路漫漫其修远兮,吾将上下而求索 文章目录 题目要求:应该支持如下操作:示例:提示: 结构体定义队列的创建基本操作判断队列是否为空…...
阿里后端实习一面面经
阿里后端实习一面面经 项目中使用到了es,es的作用? elasticsearch是一款非常强大的开源搜索引擎,具备非常多强大功能,可以帮助我们从海量数据中快速找到需要的内容 es中的重要概念? 群集:一个或多个节点…...
element-ui组件DatePicker日期选择器移动端兼容
element-ui组件DatePicker日期选择器移动端兼容 css /** 移动端展示 **/ media screen and (max-width: 500px) {.el-picker-panel__sidebar {width: 100%;}.el-picker-panel {width: 400px!important;}.el-picker-panel__content {width: 100%;}.el-picker-panel__body{marg…...
burpsuite 爆破
靶场搭建:phpstudy的安装与靶场搭建 - junlin623 - 博客园 (cnblogs.com) 账号字典:XXTK: 一些弱口令、fuzz字典 (gitee.com) 网盘链接:https://pan.baidu.com/s/1v5pAwaTwoeCnJgkUXf3iLQ?pwd=mllm 提取码:mllm --来自百度网盘超级会员V2的分享 一、暴力破解 - 基于…...
SparkSQL基础解析(三)
1、 Spark SQL概述 1.1什么是Spark SQL Spark SQL是Spark用来处理结构化数据的一个模块,它提供了2个编程抽象:DataFrame和 DataSet,并且作为分布式SQL查询引擎的作用。 我们已经学习了Hive,它是将Hive SQL转换成MapReduce然后提…...
gz-hamonic 安装提示缺少许多依赖无法安装
在软件更新源中增加gz-hamonic的软件源, 点击添加,在输入框中填入如下语句: deb http://packages.osrfoundation.org/ubuntu jammy main 如图所示: 然后执行 sudo apt -get install gz-hamonic即可安装。 如下图 在终端中输入…...
新版Edge卸载
新版Edge卸载:步骤与注意事项 随着Windows 10的发布,微软推出了新版Edge浏览器。虽然新版Edge浏览器具有许多优秀的新功能和改进,但有时您可能希望卸载它并使用其他浏览器。在本文中,我们将向您介绍如何卸载新版Edge浏览器&#…...
Ansibe自动化基础
目录 一.Ansibe自动化概述 1.特点 2.工作特性 3.应用场合 二.ansibe安装即相关文件说明 1.安装 2.相关文件 3.主配置文件内容详解 4.ansibe运行机制 三.ansibe管理节点命令 1.Ansibe 四.主机组配置 1.基本配置 第一种: 第二种: 2.设置SSH…...
2023 年中国高校大数据挑战赛赛题B DNA 存储中的序列聚类与比对-解析与参考代码
题目背景:目前往往需要对测序后的序列进行聚类与比对。其中聚类指的是将测序序列聚类以判断原始序列有多少条,聚类后相同类的序列定义为一个簇。比对则是指在聚类基础上对一个簇内的序列进行比对进而输出一条最有 可能的正确序列。通过聚类与比对将会极大…...
决策树--分类决策树
1、介绍 ① 定义 分类决策树通过树形结构来模拟决策过程,决策树由结点和有向边组成。结点有两种类型:内部结 点和叶结点。内部结点表示一个特征或属性,叶子节点表示一个类。 ② 生成过程 用决策树分类,从根结点开始ÿ…...
【2024/1/5】
2024/1/5周报 本周开展工作下周工作计划 本周开展工作 首先的话就是跟大家汇报一下上一个项目的进度,那因为一些我这边的不可控的因素暂时进行搁置,随后的话还是需要在进行做的。 因此我们最近在做一个web端的项目,这个项目的具体的就不汇报…...
CNN——VGG
1.VGG简介 论文下载地址:https://arxiv.org/pdf/1409.1556.pdf VGGNet 是由牛津大学视觉几何小组(Visual Geometry Group, VGG)提出的一种深层卷积网络结构,他们以 7.32% 的错误率赢得了 2014 年 ILSVRC 分类任务的亚军ÿ…...
深入理解Java中的多线程编程与并发控制
当谈论到 Java 编程语言时,多线程编程和并发控制是其中最重要的话题之一。Java 在多线程领域有着强大的支持和丰富的工具集,允许开发人员利用并发性来提高程序性能和效率。本文将深入探讨 Java 中的多线程编程和并发控制,包括线程的创建、同步…...
提供10个mysql的实例和思路
学生信息管理系统 学生表(id, name, gender, age, class_id)班级表(id, name)思路:通过学生表和班级表进行关联,可以实现学生信息的查询、添加、修改、删除等操作。 订单管理系统 订单表(id, us…...
FPGA项目(14)——基于FPGA的数字秒表设计
1.功能设计 设计内容及要求: 1.秒表最大计时范围为99分59. 99秒 2.6位数码管显示,分辨率为0.01秒 3.具有清零、启动计时、暂停及继续计时等功能 4.控制操作按键不超过二个。 2.设计思路 所采用的时钟为50M,先对时钟进行分频,得到100HZ频率…...
浅谈指数移动平均(ema)
经常在各种代码中看到指数移动平均(比如我专注的网络传输领域),但却不曾想到它就是诠释世界的方法,我们每个人都在被这种方式 “平均”… 今天说说指数移动平均(或移动指数平均,Exponential Moving Average)。 能查到的资料都侧重于其数学形…...
1-并发编程线程基础
什么是线程 在讨论什么是线程前有必要先说下什么是进程,因为线程是进程中的一个实体,线程本身是不会独立存在的。 进程是代码在数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,线程则是进程的一个执行路径&#…...
vue中动态出来返回的时间秒数,在多少范围显示多少秒,多少范围显示分,小时等等
在Vue中,你可以使用计算属性(computed property)或过滤器(filter)来根据动态返回的时间秒数来显示不同的时间单位,比如秒、分、小时等等。 下面是一个使用计算属性的示例: <template>&l…...
English: go through customs
文章目录 常见单词机场指示登机和中转降落以及公共服务签证篇出/入境卡篇入境英语会话篇 常见单词 customs: 海关 (kʌstəmz)cash: 现金 (kʃ)passport: 护照 (pspɔːt)luggage/baggage: 行李 (lʌɡɪdʒ/ˈbɡɪdʒ)Exchange: 换钱 (ɪks’tʃeɪndʒ)airport: 飞机场 (ɛ…...
Nginx 多端口部署多站点
目录 1.进行nginx.conf 2.复制粘贴 3.修改端口及站点根目录 4. 网站上传 1.进行nginx.conf 在 nginx 主要配置文件 nginx.conf 中,server 是负责一个网站配置的,我们想要多个端口访问的话,可以复制多个 server 先进入到 nginx.conf 中 …...
从零开始配置kali2023环境:配置jupyter的多内核环境
在kali2023上面尝试用anaconda3,anaconda2安装实现配置jupyter的多内核环境时出现各种问题,现在可以通过镜像方式解决 1. 搜索镜像 ┌──(holyeyes㉿kali2023)-[~] └─$ sudo docker search anaconda ┌──(holyeyes㉿kali2023)-[~] └─$ sudo …...
Dart调用JS对10000条定位数据滤波
使用Dart调用JS,还是为了练习跨语言调用; 一、编写对应的JS代码 平时在开发时不推荐将算法放在JS里,我这里是简单的做一下数据过滤; 首先生成一些随机定位数据,在实际开发中可以使用真实数据; // 随机定…...
大模型应用实践:AIGC探索之旅
随着OpenAI推出ChatGPT,AIGC迎来了前所未有的发展机遇。大模型技术已经不仅仅是技术趋势,而是深刻地塑造着我们交流、工作和思考的方式。 本文介绍了笔者理解的大模型和AIGC的密切联系,从历史沿革到实际应用案例,再到面临的技术挑…...
【.NET Core】异步编程模式
【.NET Core】异步编程模式 文章目录 【.NET Core】异步编程模式一、概述二、基于任务的异步模式(TAP)2.1 TAP模式命名、参数和返回类型2.2 TAP初始化异步操2.3 TAP如何编译2.4 手动生成TAP方法2.5 混合方法实现TAP2.6 TAP中Await挂起执行2.7 TAP中使用Y…...
macOS通过外置驱动器备份数据
通过外置驱动器备份数据(谨慎操作) 1.将外置驱动器连接到您的 Mac。驱动器容量应等于或大于您当前的启动磁盘。驱动器还应该是您可以抹掉的。 2.使用 macOS 恢复功能 抹掉外置驱动器,然后将 macOS 安装 到外置驱动器上。确保您选择的外置驱动…...
rtsp解析视频流
这里先说一下 播放rtsp 视频流,尽量让后端转换一下其他格式的流进行播放。因为rtsp的流需要flash支持,现在很多浏览器不支持flash。 先说一下这里我没有用video-player插件,因为它需要用flash ,在一个是我下载flash后,还是无法播放…...
【物联网】手把手完整实现STM32+ESP8266+MQTT+阿里云+APP应用——第3节-云产品流转配置
🌟博主领域:嵌入式领域&人工智能&软件开发 本节目标:本节目标是进行云产品流转配置为后面实际的手机APP的接入做铺垫。云产品流转配置的目的是为了后面能够让后面实际做出来的手机APP可以控制STM32/MCU,STM32/MCU可以将数…...
Spring Cloud Config相关问题及答案(2024)
1、什么是 Spring Cloud Config,它解决了哪些问题? Spring Cloud Config 是一个为微服务架构提供集中化外部配置支持的项目。它是构建在 Spring Cloud 生态系统之上,利用 Spring Boot 的开发便利性,简化了分布式系统中的配置管理…...
【Azure 架构师学习笔记】- Azure Databricks (4) - 使用Azure Key Vault 管理ADB Secret
本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Databricks】系列。 接上文 【Azure 架构师学习笔记】- Azure Databricks (3) - 再次认识DataBricks 前言 Azure Databricks有access token,是具有ADB内部最高权限的token。在云环境中这些高级别权限的sec…...
[每周一更]-(第50期):Go的垃圾回收GC
参考文章: https://juejin.cn/post/7111515970669117447https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-garbage-collector/https://colobu.com/2022/07/16/A-Guide-to-the-Go-Garbage-Collector/https://liangyaopei.github.io/2021/01/02/g…...
网站快速办理备案/上海外贸seo
项目做到一半,碰到个尴尬问题:PWM使用的DMA通道与串口接收的DMA通道撞车了,咋办? 考虑一下,决定放弃idle中断dma的串口不定长数据接收方案,回到中断接收去。 中断接收函数HAL_UART_RECEIVE_IT函数是个定长…...
有没有做链接的网站吗/seo策略是什么意思
hbase客户端重试机制如何保证系统的容错性和低延迟性HBase客户端Rpc的重试机制以及客户端参数优化。HBase客户端基于退避算法的重试机制1、业务用户一方面比较关注HBase本身服务的读写性能:吞吐量以及读写延迟,2、另一方面也会比较关注HBase客户端使用上…...
北京环评在那个网站上做/网络营销策划推广公司
一、File文件操作相关的类 在 java.io 包之中,用 File 类来对文件进行操作(创建、删除、取得信息等) 官方文档对于File类的说明 java.io.File 类是一个普通的类,如果要实例化对象,则常用到两个构造方法 public File(String pathname) 创建指定路径文件对象 publi…...
局网站内容建设考核/网站免费搭建
发布一个k8s部署视频:https://edu.csdn.net/course/detail/26967 课程内容:各种k8s部署方式。包括minikube部署,kubeadm部署,kubeasz部署,rancher部署,k3s部署。包括开发测试环境部署k8s,和生产…...
东营网站开发公司/惠州seo
Zipkin是一个开源分布式的追踪系统 http://zipkin.io/,在微服务架构下,能够清晰的找出系统问题所在。它同时管理数据收集和数据查询。Zipkin的设计基于Google Dagger论文 架构 查看您的平台是否已经在instrumentation, 查看列表existing instrumentation…...
建设单位网站需求报告/网站推广优化公司
概述 方法引用是用来直接访问类或实例阴茎存在的方法或者构造方法.它需要由兼容的函数式接口(lambda表达式中用到的接口)构成的目标类型上下文. 有时候, 当我们想要实现一个函数式接口的方法, 但是已经由类实现了我们想要的功能, 这时可以使用方法引用来直接使用现有的功能实现…...