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

【数据结构】循环队列原理与代码

news 来源：原创 2025/6/20 11:40:03

理论

  • 存在的意义：
    将顺序队列从逻辑上视为一个环。解决“假溢出”（出队入队连续操作后两个指针均到数组末端maxsize-1处，虽然队里没有元素但无法让元素进队）。
  • 两种定义
    1.题目是队列非空时队头指针和队尾指针分别指向队头元素和队尾元素时，则初始时front=0,rear=n-1，每次入队时rear++再放新元素。
    这种情况下 q.front=(q.rear+maxsize-q.length+1)%maxsize
    2.而队尾指针指向队尾元素的下一个时，则front=rear=0，每次入队时先放新元素再rear++;
    这种情况下 q.front==(q.rear+maxsize-q.length)%maxsize

总结：front初始只有可能为0！

  • 严蔚敏版的定义
    【严书规定】初始front=rear=0；非空队列中头指针始终指向队头，尾指针始终指向队尾的下一个位置。
    初始：Q.front=Q.rear=0;
    进队：Q.rear=(Q.rear+1)%MaxSize;
    出队：Q.front=(Q.front+1)%MaxSize;
    队列长度 (Q.rear-Q.front+MaxSize)%MaxSize;
  • 区分队满的三种解决办法
  1. 牺牲一个单元，入队时少用一个队列单元，否则队空队满的判断条件相同导致无法确定。
    队满条件：(Q.rear+1)%MaxSize==Q.front;//rear所指的单元始终为空。
    队空条件：Q.rear=Q.front;
    队列长度:(Q.rear-Q.front+MaxSize)%MaxSize;
  2. 增设表示元素个数数据成员Q.size
  3. 增设tag，删除时tag=0;入队时tag=1;当Q.front==Q.rear时可区分。（操作完后检查空满并赋值tag）

注意：出队入队之前的检查空满的条件

  • 循环链队判空：rear->next ==rear

代码练习

https://www.lintcode.com/problem/955/

class CircularQueue:def __init__(self, n):# do intialization if necessaryself.arr = [None]*nself.head, self.tail = 0, -1 #队尾先+1再放元素self.size = n"""@return:  return true if the array is full"""def isFull(self):return self.head == (self.tail + 1) % self.size and not self.arr[self.tail] is None"""@return: return true if there is no element in the array"""def isEmpty(self):return self.arr[self.tail] is None #队尾始终指向最后一个元素"""@param element: the element given to be added@return: nothing"""def enqueue(self, element):self.tail = (self.tail + 1) % self.sizeself.arr[self.tail] = element"""@return: pop an element from the queue"""def dequeue(self):ele = self.arr[self.head]self.arr[self.head] = Noneself.head = (self.head + 1) % self.sizereturn ele

相关文章：

【数据结构】循环队列原理与代码

理论 存在的意义： 将顺序队列从逻辑上视为一个环。解决“假溢出”（出队入队连续操作后两个指针均到数组末端maxsize-1处，虽然队里没有元素但无法让元素进队）。两种定义 1.题目是队列非空时队头指针和队尾指针分别指向队头元素和队…...

编程日记 2025/6/20 11:40:03

Kettle Doris Plugin编译过程

起因 公司的数据中台产品用的doris作为数据仓库，用kettle作为etl引擎，但是表输出组件太慢了。偶然有一天发现doris提供了kettle组件，但是需要自己编译，于是就开始自己编译。 坑 因为kettle的依赖包在m2（中央仓库&am…...

编程日记 2025/6/1 10:49:01

Day10 苍穹外卖项目 订单搜索、各个状态的订单统计、查询订单详细、接单、拒单、取消订单、派送订单、完成订单

目录 1.订单搜索 1.1 需求分析和设计 1.2 接口设计 1.2 代码实现 1.2.1 admin/OrderController 1.2.2 OrderService 1.2.3 OrderServiceImpl 2.各个状态的订单数量统计 2.1 需求分析和设计 2.2 接口设计 2.3 代码实现 2.3.1 admin/OrderController 2.3.2 OrderService 2.3.3 Or…...

编程日记 2025/5/30 10:22:27

你知道OSI参考模型是什么吗？

你知道OSI参考模型是什么吗？ 一. OSI模型图解二. OSI七层模型三. OSI模型的特点四. OSI模型与TCP/IP模型的对比五. 总结 前言 这是我在这个网站整理的笔记,有错误的地方请指出，关注我，接下来还会持续更新。 作者：神的孩子都在歌唱…...

编程日记 2025/5/31 5:18:47

《开源数据：开启信息共享与创新的宝藏之门》

《开源数据：开启信息共享与创新的宝藏之门》 一、开源数据概述（一）开源数据的定义（二）开源数据的发展历程 二、开源数据的优势（一）成本效益优势（二）灵活性与可定制性&…...

编程日记 2025/6/21 2:42:21

机器学习之学习范式

机器学习的四种主要范式分别是：监督学习、非监督学习、强化学习和半监督学习。以下是每种范式的详细介绍： 1. 监督学习（Supervised Learning） 定义： 通过已标注的数据训练模型，以预测或分类未知数据。 目…...

编程日记 2025/6/20 6:16:53

计算机网络技术基础：5.数据通信系统

一、数据通信的基本概念 1.信息 信息是对客观事物的运动状态和存在形式的反映，可以是客观事实的形态、大小、结构、性能等描述，也可以是客观事物与外部之间的联系。信息的载体可以是数字、文字、语音、图形和图像等。计算机及其外围设备产生和交换的信息…...

编程日记 2025/6/21 2:35:22

ubuntu下anconda装pytorch

1、禁用nouveau sudo vim /etc/modprobe.d/blacklist.conf 在文件最后部分插入以下两行内容 blacklist nouveau options nouveau modeset0 更新系统 sudo update-initramfs -u 重启系统 2、装nvidia驱动 卸载原来驱动 sudo apt-get remove nvidia-* （若安装…...

编程日记 2025/6/21 2:46:56

【深入理解MySQL索引】

深入理解MySQL索引 MySQL索引是一种数据结构，用于帮助快速查找和检索数据库表中的数据。以下是对MySQL索引的详细解释，并附有相应的代码示例以加深理解。 一、索引的原理及作用 原理：索引是以数据库表中的“列”为维度建立的，通…...

编程日记 2025/6/3 8:12:13

Linux 中批量添加cron定时任务的方法

目录 方法一：通过 crontab 命令批量添加方法二：通过直接修改 crontab 文件 方法一：通过 crontab 命令批量添加 1、先将需要添加 cron 执行的多条定时任务写入一个文本文件 例如： 0 3 * * * /bin/bash /root/work/job/MySQLBack.…...

编程日记 2025/6/21 3:11:28

【OSS】php使用oss存储

阿里云oss官方文档：文档 1、前期工作 创建阿里云账号，登录创建bucket，注意修改权限，要不然可能读取不到 申请accessKeyId和accessKeySecret accessKey 2、项目中安装OSS扩展 composer require aliyuncs/oss-sdk-php3、基础使…...

编程日记 2025/6/4 16:23:23

个人ffmpeg笔记（一）

环境安装 QT环境安装 运行qt…run安装 下载地址：https://download.qt.io/archive/qt/ 下载地址：https://download.qt.io/archive/qt/5.12/5.12.10/ sudo apt install --reinstall libxcb-xinerama0 解决xcb问题 Ubuntu16.04打开Qt显示/home/user/.co…...

编程日记 2025/6/3 0:42:55

Python的3D可视化库【vedo】2-3 (plotter模块) 增删物体、控制相机

文章目录 4 Plotter类的方法4.3 渲染器内的物体操作4.3.1 添加物体4.3.2 移除物体4.3.3 渲染器的内容列表 4.4 相机控制4.4.1 访问相机对象4.4.2 重置相机状态4.4.3 移动相机位置4.4.4 改变相机焦点4.4.5 改变相机朝向的平面4.4.5 旋转相机4.4.6 对齐相机的上朝向4.4.7 缩放 ve…...

编程日记 2025/6/20 21:57:57

关于QMessageBox的一些使用总结和避坑指南

参考学习 Qt中QMessageBox的用法—看这一篇就够了 Qt：使用QMessageBox弹出标准对话框 QMessageBox模态与非模态及QT中的exec() 如何调整QMessageBox的大小 QSS 自定义QMessageBox python QMessageBox设置标签和按钮居中、中文按钮 使用建议 经过查看多方的资料&…...

编程日记 2025/6/3 18:20:15

LearnOpenGL学习（高级OpenGL -＞ 高级GLSL，几何着色器，实例化）

高级GLSL 内建变量 顶点着色器 gl_PointSoze : float 输出变量，用于控制渲染 GL_POINTS 型图元时，点的大小。可用于粒子系统。将其设置为 gl_Position.z 时，可以使点的距离越远，大小越大。创建出类似近视眼看远处灯光的效果 gl…...

编程日记 2025/6/4 15:44:57

for X_batch, y_batch in dataloader ，其中y_batch想转成list

for X_batch, y_batch in dataloader ，其中y_batch想转成list for X_batch, y_batch in dataloader:# y_batch数据类型的是 tensor组成的list# 初始化一个空列表来存储展平后的数据y_batch_flat []# 遍历y_batch 这个list中的每个张量for tensor in y_batch:# 展平…...

编程日记 2025/6/21 2:33:03

Kruskal最小生成树算法正确性证明

Kruskal: 每次考虑最短一条边, 如果会形成回路则不选择该边, 如果不会形成回路则选择该边, 直到选出了n-1条边 要点: 每次都选择不会形成回路的最短边 数学归纳法 ① n<2时, 显然成立 ② 设n k时成立, 则当n k1时: 将图划分为 子图A(k) 和 B(1) ∵ n k时成立 ∴ A(k)可…...

编程日记 2025/6/21 3:28:25

操作系统（12）内存分配

前言 操作系统内存分配是操作系统内存管理的重要组成部分&#xff0c;涉及将物理内存分配给各个程序以使用的过程。 一、内存分配的基本概念 内存分配指的是操作系统将物理内存分配给程序以使用。操作系统通过内存分配&#xff0c;确保每个程序都能获得足够的内存资源来执行其任…...

编程日记 2025/6/21 3:20:47

oracle client linux服务器安装教程

p13390677_112040_Linux-x86-64_4of7.zip 安装前&#xff0c;确认/etc/hosts文件已配置正确 cat /etc/hosts 127.0.0.1 localhost localhost.localdomain localhost4 localhost4.localdomain4 ::1 localhost localhost.localdomain localhost6 localhost6.localdomain6 10.2…...

编程日记 2025/6/21 2:51:36

生信技能65 - SRA数据库公共数据自动化下载及SRA批量自动化拆分

根据NCBI Metadata数据表，实现SRA数据库公共数据自动化下载及SRA批量自动化拆分。 1. 程序逻辑 根据SraRunTable.csv自动从公共数据库下载SRA文件 ；模式0（默认）为下载模式，模式1为拆分模式，拆分支持进度显示；提取Metadata关键信息数据，重新写入新的文本文件。2. 运行示…...

编程日记 2025/6/4 1:10:19

ubuntu+ros新手笔记（五）：初探anaconda+cuda+pytorch

深度学习三件套&#xff1a;初探anacondacudapytorch 系统ubuntu22.04 ros2 humble 1.初探anaconda 1.1 安装 安装过程参照【详细】Ubuntu 下安装 Anaconda 1.2 创建和删除环境 创建新环境 conda create -n your_env_name pythonx.x比如我创建了一个名为“py312“的环境…...

编程日记 2025/6/4 15:28:09

下载红米Note 9 Pro5G对应的LineageOS代码下载及编译

构建 LineageOS 进入网站&#xff1a;Info about gauguin | LineageOS Wiki&#xff0c;点击&#xff1a;Build for yourself&#xff0c;里面有详细的教程&#xff0c;我这里就按照Note 9 Pro 5G来。 机器环境 Ubuntu环境为&#xff1a;20.04.6LinagesOS版本&#xff1a;21-…...

编程日记 2025/6/3 8:12:00

数据链路层(Java)(MAC与IP的区别)

以太网协议&#xff1a; "以太⽹" 不是⼀种具体的⽹络, ⽽是⼀种技术标准; 既包含了数据链路层的内容, 也包含了⼀些物理 层的内容. 例如: 规定了⽹络拓扑结构, 访问控制⽅式, 传输速率等; 例如以太⽹中的⽹线必须使⽤双绞线; 传输速率有10M, 100M, 1000M等; 以太…...

编程日记 2025/6/21 2:27:24

Unity中Mesh重叠顶点合并参考及其应用

在Unity中&#xff0c;如果将一个模型文件&#xff08;比如从max里面导出一个fbx文件&#xff09;导入到编辑器中之后&#xff0c;Unity会把所有在原来在面列表中公用的顶点复制一份&#xff0c;保证每个三角形使用的顶点都是单独的&#xff0c;不与其它三角形共用顶点&#xf…...

编程日记 2025/6/20 18:34:26

Day3——墨刀原型设计

墨刀介绍 墨刀&#xff08;Mockplus&#xff09;是一款流行的在线原型设计和协作工具&#xff0c;适用于网页和移动应用的设计。以下是墨刀的一些主要特点和功能&#xff1a; 主要特点&#xff1a; 快速原型设计&#xff1a;墨刀提供了一系列的设计工具和组件&#xff0c;可…...

编程日记 2025/6/21 3:11:28

【JAVA】Java项目实战—移动端项目：天气查询APP

在移动互联网时代&#xff0c;天气查询应用程序&#xff08;APP&#xff09;是日常生活中不可或缺的一部分。无论是出门旅行、上班通勤&#xff0c;还是安排户外活动&#xff0c;获取实时天气信息都至关重要。Java作为一种强大且广泛使用的编程语言&#xff0c;特别适合用于开发…...

编程日记 2025/6/21 3:10:25

P1208 [USACO1.3] 混合牛奶 Mixing Milk(py)

题目描述 由于乳制品产业利润很低&#xff0c;所以降低原材料&#xff08;牛奶&#xff09;价格就变得十分重要。帮助 Marry 乳业找到最优的牛奶采购方案。 Marry 乳业从一些奶农手中采购牛奶&#xff0c;并且每一位奶农为乳制品加工企业提供的价格可能相同。此外&#xff0c…...

编程日记 2025/6/3 10:35:39

day13 python（1）——python基础

【没有所谓的运气&#x1f36c;&#xff0c;只有绝对的努力✊】 1、python简介 1.1 为什么学习python 1.2 python发展历史 python2.x和python3.x 版本里面有些是不兼容的。&#xff08;我自己本地版本 3.11&#xff09; 2、语言的分类 &#xff08;1&#xff09;编译型 …...

编程日记 2025/6/21 2:53:46

Tomcat原理（5）——tomcat最终实现

目录 一、什么是Servlet容器 二、ServletConfigMapping构建实现容器 ServletConfigMapping MyTomcat 三、优化server Server MyTomcat 四、匹配 代码如下&#xff1a; 测试如下&#xff1a; 上一篇博客已经为介绍了servelet的实现 &#xff0c;这篇对上一篇博客进行补…...

编程日记 2025/6/21 2:27:24

善战者与细

《孙子兵法》说&#xff1a;善战者无赫赫战功。 《道德经》说&#xff1a;天下大事必做于细。 这两句话&#xff0c;可以结合来思考。如果&#xff0c;我们把事业&#xff0c;拆解为多个小项目&#xff0c;小项目拆解为小行动&#xff0c;也就是天下大事作于细。这种情况下&am…...

编程日记 2025/6/21 2:24:05

sqli-labs靶场第26-30关

第26关 这关将逻辑运算符&#xff0c;注释符以及空格给过滤了 我们先使用单引号进行闭合 这时我们查看源代码可以看到这一关过滤了很多字符 可以看到这里将or and / -- # 空格等字符都被注释了 空格被过滤了我们可以使用()来代替&#xff0c;and和or可以使用双写来绕过 因为…...

编程日记 2025/6/21 3:19:30

ffmpeg和ffplay命令行实战手册

文章目录 视频拼接用concat视频分段拼接(ffplay 不可调用seek函数进行seek)给视频添加黑边&#xff0c;让视频填充并居中显示不同分辨率视频分段拼接&#xff0c;并且&#xff0c;设置单个视频的缩放比例和摆放位置视频画中画复杂嵌套用overlay(ffplay 可调用seek函数进行seek)…...

编程日记 2025/6/20 10:22:53

240004】基于maven的java+ssm+mysql的房屋租赁系统的设计与实现

基于ssmmavenmysql的房屋租赁系统的设计与实现 1.项目描述2.运行环境3.项目截图4.源码获取 1.项目描述 该项目在原有的基础上进行了优化&#xff0c;包括新增了注册功能&#xff0c;房屋模糊查询功能&#xff0c;管理员和用户信息管理等功能&#xff0c;以及对网站界面进行了优…...

编程日记 2025/6/3 10:35:17

2.metagpt中的软件公司智能体 (ProductManager 角色)

1. 代码 ProductManager 类 from metagpt.actions import UserRequirement, WritePRD from metagpt.actions.prepare_documents import PrepareDocuments from metagpt.roles.role import Role, RoleReactMode from metagpt.utils.common import any_to_nameclass ProductMan…...

编程日记 2025/6/3 8:11:44

MOS管振铃现象

1&#xff0c;什么是振铃 用MOS管作为电子开关电路如下 单片机输出的PWM波形应该是规整的方波信号。但实际上确出现了下图的不稳定波形。这种上升沿和下降沿出现的不同程度的一小段震荡就叫做MOS管的振铃。如果振铃的峰值超过G端耐压&#xff0c;GS之间就会被击穿&#xff0c;…...

编程日记 2025/6/19 23:03:21

docker简单命令

docker images 查看镜像文件 docker ps -a 查看容器文件 docker rm 0b2 删除容器文件&#xff0c;id取前三位即可 docker rmi e64 删除镜像文件&#xff08;先删容器才能删镜像&#xff09;&#xff0c;id取前三位即可 在包含Dockerfile文件的目录…...

编程日记 2025/6/2 11:45:42

XML基础学习

参考文章链接： XML基础学习 在w3school看到了XML的教程，想到以前工作学习中也接触到了XML，但只是简单搜索了解了下，没有认真去学习XML的基础，所以现在认真看下其基础部分，并写篇博客作为笔记记录下。 XML 简介 XML 被设计用来传输和存储数据。 什么是 XML? XML 指可…...

编程日记 2025/6/21 3:00:27

ARMS 用户体验监控正式发布原生鸿蒙应用 SDK

作者&#xff1a;杨兰馨&#xff08;楠瑆&#xff09; 背景 2024 年 10 月 22 日&#xff0c;华为正式发布了原生鸿蒙操作系统&#xff08;HarmonyOS NEXT&#xff09;。原生鸿蒙实现了系统底座全部自研&#xff0c;系统的流畅度、性能、安全特性等方面显著提升&#xff0c;也…...

编程日记 2025/6/3 8:11:25

如何使用微调后的Lora适配器？

Lora&#xff08;Low-Rank Adaptation&#xff09; 是一种高效的模型微调方法&#xff0c;尤其在自然语言处理和生成任务中得到了广泛应用。与传统的微调方法相比&#xff0c;Lora方法通过低秩适配器的方式&#xff0c;使得模型微调更为高效&#xff0c;且资源消耗更少。本文将…...

编程日记 2025/6/21 3:00:28

HAL 库：创建hal首要配置内容

第一步配置SYS&#xff08;system系统&#xff09; Debug&#xff08;调试&#xff09;&#xff1a; Serial Wire 串行线&#xff08;要用stick&#xff09; Timebase Source&#xff1a;时基源 第二步配置RCC&#xff08;reset and clodk controler&#xff09;复位和时钟控…...

编程日记 2025/6/3 6:14:04

YOLOv9-0.1部分代码阅读笔记-experimental.py

experimental.py models\experimental.py 目录 experimental.py 1.所需的库和模块 2.class Sum(nn.Module): 3.class MixConv2d(nn.Module): 4.class Ensemble(nn.ModuleList): 5.def attempt_load(weights, deviceNone, inplaceTrue, fuseTrue): 1.所需的库和模块…...

编程日记 2025/6/4 1:09:20

如何高效获取Twitter数据：Apify平台上的推特数据采集解决方案

引言 在数据分析和市场研究领域&#xff0c;Twitter&#xff08;现在的X&#xff09;数据一直是重要的信息来源。但是&#xff0c;自从Twitter更改API定价策略后&#xff0c;获取数据的成本大幅提升。本文将介绍一个经济实惠的替代方案。 为什么需要Twitter数据&#xff1f; …...

编程日记 2025/6/19 21:07:42

【蓝凌表单】JSP组件常用语法整理

JSP组件常用语法整理 必填非必填写法//必填 $("[name=extendDataFormInfo.value(fd_344677482769e2)]").attr("validate","requiredvalue"); //非必填 $(...

编程日记 2025/6/4 11:27:34

设定“例外规则”：不完美也是完美

完美主义是一种追求极致的心态&#xff0c;它驱使我们不断追求更高的标准和更好的结果。然而&#xff0c;生活并不总是按照我们的计划进行&#xff0c;有时候我们需要灵活应对&#xff0c;设定一些“例外规则”来适应那些不完美的时刻。以下是一些实际的例子&#xff0c;展示如…...

编程日记 2025/6/4 1:37:41

01《Python数据分析》数据分析初探章节总结

目录 1 概述1.1 数据分析定义1.2 数据分析目标1.3 数据分析分类 2 数据分析方法3 数据分析流程4 寻找问题原因5 典型问题参考学习 1 概述 1.1 数据分析定义 数据分析1就是&#xff1a;用适当的统计分析方法对收集来的大量数据进行分析&#xff0c;提取有用信息和形成结论&…...

编程日记 2025/6/2 23:10:13

java web 实验五 Servlet控制层设计（设计性）

实验五 Servlet控制层设计&#xff08;设计性&#xff09; //代码放在资源包里了 实验目的 熟悉Servlet的基本语法。掌握采用HTML、JS、JDBC、JSP、Servlet和四层结构的综合应用。实验要求 本实验要求每个同学单独完成&#xff1b;调试程序要记录调试过程中出现的问题及解决…...

编程日记 2025/6/2 23:10:11

Timestamp Unix时间戳在线转换 - 加菲工具

Timestamp Unix时间戳在线转换 打开网站 加菲工具 选择“时间戳转换” 或者直接打开&#xff1a; https://www.orcc.online/tools/timestamp 在前半部分输入框输入时间/时间戳&#xff0c;点击“转换>>”按钮&#xff0c;即可转换完成 得到转换结果...

编程日记 2025/6/2 23:10:09

ABAP 订单多次开票，显示多张开票凭证

一、业务背景 在实际业务上&#xff0c;同一笔销售订单可能分多次发货&#xff0c;多次开票&#xff0c;因此再销售订单状态报表上就要体现该过程&#xff1a;对于同一张销售订单&#xff0c;分多次开票时&#xff0c;按照发票和订单行项目&#xff0c;显示开票数量与为开票数…...

编程日记 2025/6/21 0:59:40

源码安装编译gcc-12

下载gcc12 https://link.zhihu.com/?targethttps%3A//github.com/gcc-mirror/gcc/archive/refs/tags/releases/gcc-12.2.0.tar.gz 解压并执行相关依赖下载 ./contrib/download_prerequisites make && make install 默认装在/usr/local下&#xff0c; 如果要自己指定…...

编程日记 2025/6/2 23:10:04

VGGNet：深度学习中的卷积神经网络经典之作

目录 ​编辑 引言 VGGNet的历史背景 VGGNet的特点 1. 深度网络结构 2. 小卷积核的使用 3. 多尺度训练 4. 参数量的优化 5. 去除局部响应归一化 6. 优秀的特征提取能力 VGGNet的应用案例 VGGNet的代码复现 代码解析 结论 引言 在深度学习的浪潮中&#xff0c;卷积…...

编程日记 2025/6/4 1:23:37