当前位置: 首页 > news >正文

设计循环队列——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 相等,则队列为空
}

frontback 相等时,队列为空。

判断队列是否已满:

// 检查队列是否已满
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 路漫漫其修远兮,吾将上下而求索 文章目录 题目要求:应该支持如下操作:示例:提示: 结构体定义队列的创建基本操作判断队列是否为空&#xf…...

阿里后端实习一面面经

阿里后端实习一面面经 项目中使用到了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、介绍 ① 定义 分类决策树通过树形结构来模拟决策过程,决策树由结点和有向边组成。结点有两种类型:内部结 点和叶结点。内部结点表示一个特征或属性,叶子节点表示一个类。 ② 生成过程 用决策树分类,从根结点开始&#xff…...

【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 分类任务的亚军&#xff…...

深入理解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中&#xff0c;你可以使用计算属性&#xff08;computed property&#xff09;或过滤器&#xff08;filter&#xff09;来根据动态返回的时间秒数来显示不同的时间单位&#xff0c;比如秒、分、小时等等。 下面是一个使用计算属性的示例&#xff1a; <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 中&#xff0c;server 是负责一个网站配置的&#xff0c;我们想要多个端口访问的话&#xff0c;可以复制多个 server 先进入到 nginx.conf 中 …...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...