设计循环队列——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 中 …...

大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...

华为OD机考-机房布局
import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

麒麟系统使用-进行.NET开发
文章目录 前言一、搭建dotnet环境1.获取相关资源2.配置dotnet 二、使用dotnet三、其他说明总结 前言 麒麟系统的内核是基于linux的,如果需要进行.NET开发,则需要安装特定的应用。由于NET Framework 是仅适用于 Windows 版本的 .NET,所以要进…...
6.计算机网络核心知识点精要手册
计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法:数据与控制信息的结构或格式,如同语言中的语法规则语义:控制信息的具体含义和响应方式,规定通信双方"说什么"同步:事件执行的顺序与时序…...
GB/T 43887-2024 核级柔性石墨板材检测
核级柔性石墨板材是指以可膨胀石墨为原料、未经改性和增强、用于核工业的核级柔性石墨板材。 GB/T 43887-2024核级柔性石墨板材检测检测指标: 测试项目 测试标准 外观 GB/T 43887 尺寸偏差 GB/T 43887 化学成分 GB/T 43887 密度偏差 GB/T 43887 拉伸强度…...
【学习记录】使用 Kali Linux 与 Hashcat 进行 WiFi 安全分析:合法的安全测试指南
文章目录 📌 前言🧰 一、前期准备✅ 安装 Kali Linux✅ 获取支持监听模式的无线网卡 🛠 二、使用 Kali Linux 进行 WiFi 安全测试步骤 1:插入无线网卡并确认识别步骤 2:开启监听模式步骤 3:扫描附近的 WiFi…...
云原生技术驱动 IT 架构现代化转型:企业实践与落地策略全解
📝个人主页🌹:慌ZHANG-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、背景:IT 架构演进的战略拐点 过去十年,企业 IT 架构经历了从传统集中式架构到分布式架构的转型。进入云计算…...