栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java数组模拟的队列是环形队列

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java数组模拟的队列是环形队列

背景

队列有两种实现方式:1、数组,2 、链表

在数组实现队列时,有的教科书中只说了队列满的条件是 (rear + 1) % manSize = front

这个公式真让人摸不着头脑

原来:这是数组模拟环形队列,才有的结果

队头 front :初始值为0,指向队列的第一个元素

队尾 rear : 初始值为0 ,指向队列最后一个元素的下一位

对照以下环形图分析:当空队列新增一个元素时,rear++ ,rear变成1, 数组0的位置用于存放数据,rear不存放数据。

此时,如果再新增一个元素。rear++ ,rear变成2,数组1的位置存放数据。

队列满的条件是 (rear + 1) % manSize = front 由于rear留空,所以maxSize为8的数组,最多只能存放7位。当 rear为7时,(7+1)%8 = 0

队列中有效数据的个数是 (rear-front+maxSize)%manSize

由于是环形队列,所以rear 可能比front小,比如 rear = 1 ,front = 6 ,加上 maxSize 为了不用取绝对值,实际是|rear-front|%manSize,因为绝对值要调用Math的包。

可以对照的环形图来数,rear不保存值,得到是3个元素。

套用公式 (1-6+8)%8 = 3 % 8 = 3

为了便于理解,我画了一个同心圆

数组初始化时,需要指定manSize

队尾留空,不存任何数据,所以8个元素的数据,存放的队列数据是7个

暂时记录在此,以后有补充再更新~

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/768570.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号