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

【数据结构】环形队列

环形队列

1. 定义

环形队列就是将队列在逻辑上看作环形结构、物理上仍是数组形式存储的一种数据结构。

其实现主要分为两种情况:

  1. 浪费空间法
  2. 记录空间法

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 == headhead == tail
标记长度法used == sizeused == 0

其中推荐使用标记长度法。

相关文章:

【数据结构】环形队列

环形队列 1. 定义 环形队列就是将队列在逻辑上看作环形结构、物理上仍是数组形式存储的一种数据结构。 其实现主要分为两种情况&#xff1a; 浪费空间法记录空间法 2. 实现 实现要考虑的是成员变量 2.1 记录空间法 使用used标识当前存储了多少元素&#xff0c;如果为空&a…...

嵌入式C编码规范

嵌入式C编码规范 编码规范&#xff0c;没有最好&#xff0c;只有最合适&#xff0c;有但不执行不如没有。 嵌入式C编码规范 https://mp.weixin.qq.com/s/z4u3YnF6vdQ1olsLeF-y_A 更多嵌入式信息请关注微信公众号【嵌入式系统】...

Golang 并发 — 流水线

并发模式 我们可以将流水线理解为一组由通道连接并由 goroutine 处理的阶段。每个阶段都被定义为执行特定的任务&#xff0c;并按顺序执行&#xff0c;下一个阶段在前一个阶段完成后开始执行。 流水线的另一个重要特性是&#xff0c;除了连接在一起&#xff0c;每个阶段都使用…...

Elasticsearch:什么是非结构化数据?

非结构化数据定义 非结构化数据是指未按照设计的模型或结构组织的数据。 非结构化数据通常被归类为定性数据&#xff0c;可以是人类或机器生成的。 非结构化数据是最丰富的可用数据类型&#xff0c;经过分析后&#xff0c;可用于指导业务决策并在许多其他用例中实现业务目标。…...

15:00的面试,15:06就出来了,问的问题过于变态了。。。

从小厂出来&#xff0c;没想到在另一家公司又寄了。 到这家公司开始上班&#xff0c;加班是每天必不可少的&#xff0c;看在钱给的比较多的份上&#xff0c;就不太计较了。没想到5月一纸通知&#xff0c;所有人不准加班&#xff0c;加班费不仅没有了&#xff0c;薪资还要降40%…...

Web自动化测试怎么做?Web网页测试全流程解析

1、功能测试 web网页测试中的功能测试&#xff0c;主要测试网页中的所有链接、数据库连接、用于在网页中提交或获取用户信息的表单、Cookie 测试等。 &#xff08;1&#xff09;查看所有链接&#xff1a; 测试从所有页面到被测特定域的传出链接。 测试所有内部链接。 测…...

MySQL数据库SQLSTATE[22007]: Invalid datetime format 日期类型不能为空值的解决办法

如果你的数据库是mysql&#xff0c; 如果你创建表或插入数据时遇到的BUG–它长这样&#xff1a; Invalid datetime format: 1292 Incorrect datetime value: ‘’ for column ‘xxx’ at row 1 或 1067 - Invalid default value for ‘xx’ 那么我将赐予你 两套剑法: &#…...

搬运工让你分分钟了解Web接口测试

01、什么是接口 百度说&#xff1a;接口泛指实体把自己提供给外界的一种抽象化物&#xff08;可以为另一实体&#xff09;&#xff0c;用以由内部操作分离出外部沟通方法&#xff0c;使其能被内部修改而不影响外界其他实体与其交互的方式 上面这句有点抽象&#xff0c;网上的…...

作业12.5

1.定义一个基类 Animal&#xff0c;其中有一个虛函数perform&#xff08;)&#xff0c;用于在子类中实现不同的表演行为。 #include <iostream>using namespace std; class Animal { private:int weight; public:Animal(){}Animal(int weight):weight(weight){}virtual …...

leetCode 47. 全排列 II + 回溯算法 + 图解 + 笔记

给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列 示例 1&#xff1a; 输入&#xff1a;nums [1,1,2] 输出&#xff1a; [[1,1,2],[1,2,1],[2,1,1]] 示例 2&#xff1a; 输入&#xff1a;nums [1,2,3] 输出&#xff1a;[[1,2,3],[1,3,2…...

Maya 2024(3D建模、动画和渲染软件)

Maya 2024是一款非常强大的3D建模、动画和渲染软件&#xff0c;它提供了许多新功能和改进&#xff0c;以帮助建模师、动画师和渲染师更加高效地进行创作。 在建模方面&#xff0c;Maya 2024引入了Symmetry&#xff08;对称&#xff09;功能&#xff0c;可以在网格两侧生成均匀…...

C++作业5

完成沙发床的多继承&#xff08;有指针成员&#xff09; 代码&#xff1a; #include <iostream>using namespace std;class Bed { private:double *money; public:Bed(){cout << "Bed::无参构造函数" << endl;}Bed(double money):money(new doub…...

Go语言很难吗?为什么 Go 岗位这么少?

其实这个话题已经躺在我的 TODO 里很久了&#xff0c;近来很多社区的小伙伴都私下来交流&#xff0c;也有在朋友圈看吐槽 Go 上海的大会没什么人。还不如 Rust 大会&#xff0c;比较尴尬。 今天主要是从个人角度看看为什么 Go 岗位看起来近来很难的样子&#xff1f; 盘一下数…...

为什么要替换 Object.defineProperty?

目录 前言&#xff1a;为什么要替换 Object.defineProperty&#xff1f; 详解&#xff1a;为什么要替换 Object.defineProperty&#xff1f; 总结&#xff1a; 前言&#xff1a;为什么要替换 Object.defineProperty&#xff1f; JavaScript中的Object.defineProperty是一种…...

百马百担c语言编程

以下是一个百马百担问题的C语言编程实现&#xff1a; #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中&#xff0c;连续包换运算符reg的次数&#xff1a; #include <iostream>//return 返回匹配的字符个数 //buf, 要检测的字符串 //reg, 包含的连续运算符 int GetMatchCount(std::string& buf, std::string& reg) {int nMatchCount 0;if (reg.…...

前端依赖下载速度过慢解决方法,nrm 镜像管理工具

npm 默认镜像 &#xff1a;https://registry.npmjs.org/ 问题 使用 npm install 安装依赖的时候&#xff0c;受网络的限制&#xff0c;速度会很慢。 解决 使用国内镜像代理。 nrm nrm 是镜像源管理工具&#xff1b; 1. 安装 nrm npm install nrm --global# 查看镜像源列…...

如何为 3D 模型制作纹理的最佳方法

在线工具推荐&#xff1a; 3D数字孪生场景编辑器 - GLTF/GLB材质纹理编辑器 - 3D模型在线转换 - Three.js AI自动纹理开发包 - YOLO 虚幻合成数据生成器 - 三维模型预览图生成器 - 3D模型语义搜索引擎 您可以通过不同的方式为 3D 模型创建 3D 纹理。下面我们将介绍为 3D …...

智慧校园:TSINGSEE青犀智能视频监控系统,AI助力优化校园管理

随着科技的飞速发展和信息化社会的到来&#xff0c;智慧校园已经成为教育领域的一种新型发展模式。智慧校园的需求和发展趋势日益显现&#xff0c;其建设已成为当今教育信息化发展的重要方向。 TSINGSEE青犀结合高可靠、高性能的云计算、人工智能、大数据、物联网等技术&#…...

Three的lod技术

1、资源&#xff1a;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 }…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...