【数据结构】环形队列
环形队列
1. 定义
环形队列就是将队列在逻辑上看作环形结构、物理上仍是数组形式存储的一种数据结构。
其实现主要分为两种情况:
- 浪费空间法
- 记录空间法
2. 实现
实现要考虑的是成员变量
2.1 记录空间法
使用used标识当前存储了多少元素,如果为空,那么就将head移到0位置处,如果满了,那么就将tail移到0位置处

1. 入队
队列是从队尾入,队头出,所以就是在tail的位置入队,每入一个元素就将tail++,当满的时候就将tail恢复到队头。
普通情况:

队列满了:
这时就需要tail=0,等待某个时候有元素出队,这个时候新插入的元素就又能在tail的位置进行插入。
出队操作与入队操作对称,同理。
2. 代码实现
package MyCircleQueue;public class CircleQueue {int size = 5;// 队列最大容量int used = 0;// 队列已使用元素int[] data = new int[size];// 存储队列数据int tail = 0, head = 0;// 队列头尾指针public void offer(int val) {// 满了if (used == size) {tail = 0;System.out.println("满了");return;}// 没满data[tail++] = val;used++;System.out.println("存入"+val);}public int poll() {if (used == 0) {head = 0;System.out.println("空了");return -1;}int ret = data[head++];used--;System.out.println("取出:"+ret);return ret;}
}
2.2 浪费空间法
在这种方式中,我们只使用头尾两个指针进行计算,并将 head = tail 的情况记作空,将 (tail+1)%size = head 的情况记作满。
2.2.1实现代码:
package MyCircleQueue;public class CircleQueue2 {int size = 5;int[] data = new int[size];int head= 0, tail = 0;public void offer(int val) {if ((tail+1) % size == head) {System.out.println("满了");return;}data[tail++] = val;System.out.println("入队:"+val);}public int poll() {if (head == tail) {System.out.println("空了");return -1;}int ret = data[head++];System.out.println("出队:"+ret);return ret;}
}
3. 测试代码:
package MyCircleQueue;public class Test {public static void main(String[] args) {CircleQueue queue = new CircleQueue();for (int i = 0; i < 10; i++) {queue.offer(i);}for (int i = 0; i < 10; i++) {int ret = queue.poll();}}
}
4. 结论
环形队列分为两种实现方式:
| 方法 | 满的标记 | 空的标记 |
|---|---|---|
| 浪费空间法 | (tail+1)%size == head | head == tail |
| 标记长度法 | used == size | used == 0 |
其中推荐使用标记长度法。
相关文章:
【数据结构】环形队列
环形队列 1. 定义 环形队列就是将队列在逻辑上看作环形结构、物理上仍是数组形式存储的一种数据结构。 其实现主要分为两种情况: 浪费空间法记录空间法 2. 实现 实现要考虑的是成员变量 2.1 记录空间法 使用used标识当前存储了多少元素,如果为空&a…...
嵌入式C编码规范
嵌入式C编码规范 编码规范,没有最好,只有最合适,有但不执行不如没有。 嵌入式C编码规范 https://mp.weixin.qq.com/s/z4u3YnF6vdQ1olsLeF-y_A 更多嵌入式信息请关注微信公众号【嵌入式系统】...
Golang 并发 — 流水线
并发模式 我们可以将流水线理解为一组由通道连接并由 goroutine 处理的阶段。每个阶段都被定义为执行特定的任务,并按顺序执行,下一个阶段在前一个阶段完成后开始执行。 流水线的另一个重要特性是,除了连接在一起,每个阶段都使用…...
Elasticsearch:什么是非结构化数据?
非结构化数据定义 非结构化数据是指未按照设计的模型或结构组织的数据。 非结构化数据通常被归类为定性数据,可以是人类或机器生成的。 非结构化数据是最丰富的可用数据类型,经过分析后,可用于指导业务决策并在许多其他用例中实现业务目标。…...
15:00的面试,15:06就出来了,问的问题过于变态了。。。
从小厂出来,没想到在另一家公司又寄了。 到这家公司开始上班,加班是每天必不可少的,看在钱给的比较多的份上,就不太计较了。没想到5月一纸通知,所有人不准加班,加班费不仅没有了,薪资还要降40%…...
Web自动化测试怎么做?Web网页测试全流程解析
1、功能测试 web网页测试中的功能测试,主要测试网页中的所有链接、数据库连接、用于在网页中提交或获取用户信息的表单、Cookie 测试等。 (1)查看所有链接: 测试从所有页面到被测特定域的传出链接。 测试所有内部链接。 测…...
MySQL数据库SQLSTATE[22007]: Invalid datetime format 日期类型不能为空值的解决办法
如果你的数据库是mysql, 如果你创建表或插入数据时遇到的BUG–它长这样: Invalid datetime format: 1292 Incorrect datetime value: ‘’ for column ‘xxx’ at row 1 或 1067 - Invalid default value for ‘xx’ 那么我将赐予你 两套剑法: &#…...
搬运工让你分分钟了解Web接口测试
01、什么是接口 百度说:接口泛指实体把自己提供给外界的一种抽象化物(可以为另一实体),用以由内部操作分离出外部沟通方法,使其能被内部修改而不影响外界其他实体与其交互的方式 上面这句有点抽象,网上的…...
作业12.5
1.定义一个基类 Animal,其中有一个虛函数perform(),用于在子类中实现不同的表演行为。 #include <iostream>using namespace std; class Animal { private:int weight; public:Animal(){}Animal(int weight):weight(weight){}virtual …...
leetCode 47. 全排列 II + 回溯算法 + 图解 + 笔记
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列 示例 1: 输入:nums [1,1,2] 输出: [[1,1,2],[1,2,1],[2,1,1]] 示例 2: 输入:nums [1,2,3] 输出:[[1,2,3],[1,3,2…...
Maya 2024(3D建模、动画和渲染软件)
Maya 2024是一款非常强大的3D建模、动画和渲染软件,它提供了许多新功能和改进,以帮助建模师、动画师和渲染师更加高效地进行创作。 在建模方面,Maya 2024引入了Symmetry(对称)功能,可以在网格两侧生成均匀…...
C++作业5
完成沙发床的多继承(有指针成员) 代码: #include <iostream>using namespace std;class Bed { private:double *money; public:Bed(){cout << "Bed::无参构造函数" << endl;}Bed(double money):money(new doub…...
Go语言很难吗?为什么 Go 岗位这么少?
其实这个话题已经躺在我的 TODO 里很久了,近来很多社区的小伙伴都私下来交流,也有在朋友圈看吐槽 Go 上海的大会没什么人。还不如 Rust 大会,比较尴尬。 今天主要是从个人角度看看为什么 Go 岗位看起来近来很难的样子? 盘一下数…...
为什么要替换 Object.defineProperty?
目录 前言:为什么要替换 Object.defineProperty? 详解:为什么要替换 Object.defineProperty? 总结: 前言:为什么要替换 Object.defineProperty? JavaScript中的Object.defineProperty是一种…...
百马百担c语言编程
以下是一个百马百担问题的C语言编程实现: #include <stdio.h>int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); int a[n], b[m], c[k]; for (int i 0; i < n; i) { scanf("%d", &a[i]);…...
C++检测字符串中有效的括号个数
匹配一个字符串buf中,连续包换运算符reg的次数: #include <iostream>//return 返回匹配的字符个数 //buf, 要检测的字符串 //reg, 包含的连续运算符 int GetMatchCount(std::string& buf, std::string& reg) {int nMatchCount 0;if (reg.…...
前端依赖下载速度过慢解决方法,nrm 镜像管理工具
npm 默认镜像 :https://registry.npmjs.org/ 问题 使用 npm install 安装依赖的时候,受网络的限制,速度会很慢。 解决 使用国内镜像代理。 nrm nrm 是镜像源管理工具; 1. 安装 nrm npm install nrm --global# 查看镜像源列…...
如何为 3D 模型制作纹理的最佳方法
在线工具推荐: 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 您可以通过不同的方式为 3D 模型创建 3D 纹理。下面我们将介绍为 3D …...
智慧校园:TSINGSEE青犀智能视频监控系统,AI助力优化校园管理
随着科技的飞速发展和信息化社会的到来,智慧校园已经成为教育领域的一种新型发展模式。智慧校园的需求和发展趋势日益显现,其建设已成为当今教育信息化发展的重要方向。 TSINGSEE青犀结合高可靠、高性能的云计算、人工智能、大数据、物联网等技术&#…...
Three的lod技术
1、资源:https://sbcode.net/threejs/lod/ import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls import Stats from three/examples/jsm/libs/stats.module import { GUI } from dat.gui import { GLTFLoader }…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...
