java中用数组实现环形队列的示例代码
本篇文章主要讲述了使用数组实现环形队列的思路以及具体代码
一、队列是什么
我们先来看下百科的解释:
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
总结起来两点:
1.一种线性表
2.添加操作只能在表尾,删除操作在表头(先进先出)
二、实现队列的思路
1.初始化一个空队列
初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其实这种初始化头指针指向的是队首,尾指针指向的是队尾的后一个元素。
2.往队列里添加元素
往队列里添加元素,尾指针后移一位。
一直添加直到队列满
这个时候尾指针已经出现在数组下标外了
3.消费队列元素
每消费一个队列元素,头指针指向的元素出队,并且后移一位
再消费两个
这个时候我们想往队列里继续添加元素,尾指针后移,然后发现出现了假溢出的情况,因为尾指针无法再向后移动,而队列实际上并没有满,我们又无法继续往队列里添加数据。这个时候其实有两种解决方案。
方案一:我们每消费一个元素,其后面的元素都整体往前移动一位,就像我们生活中排队打饭一样,后面的人都往前挪一挪。但这种方案带来的后果是,带来的时间开销太大,因为基本上要操作所有的元素,所以这种方案不可行。
方案二:尾指针在指向下表为最后一个元素时,再添加元素,如果还有空位,就将尾指针重新指向0,头指针在取到下表数组末尾时,如果前面还有元素,头指针也指向0,这就是我们说的环形队列。
三、实现环形队列
1.环形队列示例图
尾指针重新指向零
再添加一个元素
连续消费三个元素,如果前面还有元素,头指针也指向0
这个时候我们发现那个原来熟悉的队列又回来了。
2.代码实现
/** * description:数组实现环形队列 * author: xiaowang * */ public class MyQueue<E> { // 队列最大个数 private int size; // 元素真实个数 private int number; // 头指针,指向队列的第一个元素即队头 private int front; // 尾指针,指向队尾的后一个元素(非队尾) private int rear; // 队列具体值 private Object[] values; // 队列满标记,当队列是满的时候为true private boolean isFullFlag; /**构造器*/ public MyQueue(int size){ if (size<0){ throw new RuntimeException("初始化队列时,队列最大元素个数不能为负"); } this.front = 0; this.rear = 0; this.number = 0; this.isFullFlag = false; this.size = size; this.values = new Object[size]; } /**往队列里添加元素 添加成功返回true 失败返回false*/ public boolean addToQueue(E e){ // 判断队列是否已经满了 if (isFullFlag){ System.out.println("队列已满,无法继续添加元素"); return false; } // 添加元素 values[rear] = e; // 元素个数加一 number++; // 尾指针后移一位,若已经指向数组最后的下表,则重新指向0 if (rear == size-1){ rear = 0; }else{ rear++; } // 添加完这个元素,判断队列是否已经满了,若满则标记为true if (rear==front){ isFullFlag = true; } return true; } /**从队列里取出数据,队头数据*/ public E getFromQueue(){ // 判断队列是否为空 if (number==0||size==0){ System.out.println("队列为空,无法从队列中获取数据"); return null; } // 临时变量 E e = (E) values[front]; // 队头置空 values[front] = null; // 个数减一 number--; // 头指针后移,若已经指向数组最后的下表,则重新指向0 if (front==size-1){ front = 0; }else { front++; } // 取队列之前若是满的状态,则更新状态 if (isFullFlag){ isFullFlag = false; } return e; } /**获取目前有几个元素正在进行排队*/ public int getNumber(){ return number; } /**获取队列的最大个数*/ public int getSize(){ return size; } /**查看队列在数组里保存的详细情况*/ public String toString(){ StringBuffer valueStr = new StringBuffer(); valueStr.append("["); for (int i = 0; i < size; i++) { if (i!=size-1){ valueStr.append(values[i]+","); }else{ valueStr.append(values[i]+"]"); } } return valueStr.toString(); } }
测试代码
public class TestQueue { public static void main(String[] args) { MyQueue<String> queue = new MyQueue<String>(5); Scanner scanner = new Scanner(System.in); Scanner scanner2 = new Scanner(System.in); boolean isCan = true; while (isCan){ System.out.println("欢迎来到小王排队系统,您可以使用以下功能。\n添加:1;取出:2;展示:3;获取排队个数:4;退出:0。"); int flag = scanner.nextInt(); switch (flag){ case 1 : System.out.println("请输入一个数据:"); String data = scanner2.nextLine(); boolean isSuccess = queue.addToQueue(data); if (isSuccess){ System.out.println("添加成功~~~"); } break; case 2 : String dataFromQueue = queue.getFromQueue(); if (dataFromQueue!=null){ System.out.println("本次取出的数据为:"+dataFromQueue); } break; case 3 : System.out.println("队列详情为:\n"+queue.toString()); break; case 4 : System.out.println("目前有"+queue.getNumber()+"个元素正在进行排队"); break; default: isCan = false; System.out.println("已退出..."); break; } } } }
总结
到此这篇关于java中用数组实现环形队列的示例代码的文章就介绍到这了,更多相关java 数组环形队列内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
- 在php中eval是一个函数并且不能直接禁用了,但eval函数又相当的危险了经常会出现一些问题了,今天我们就一起来看看eval函数对数组的操作 例子, <?php $data="array...2016-11-25
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了Python 图片转数组,二进制互转操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 本文章提供在量的数据中级操作实例有如对键名比较计算数组的差集 计算差集 给指定数组中插入一个元素 反转数组 交集赋值新的数组实例。 //定义回调函数 funct...2016-11-25
- 这篇文章主要介绍了C#二维数组基本用法,以实例形式分析了C#中二维数组的定义、初始化、遍历及打印等用法,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 下面一段代码给大家介绍php curl模拟post请求的示例代码,具体代码如下: <?php$uri = "http://www.cnblogs.com/test.php";//这里换成自己的服务器的地址// 参数数组$data = array ( 'name' => 'tanteng'// 'passwor...2015-11-24
- Array数组在C#中同样是最基本的数据结构,下面为大家C#数组的常用操作方法小结,皆为细小的代码段,欢迎收看收藏...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 下面小编就为大家带来一篇C# 拷贝数组的几种方法(总结)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 本文记录的要实现的功能类似于 MySQL 中的 ORDER BY,上个项目中有遇到这样的一个需求。 要求:从两个不同的表中获取各自的4条数据,然后整合(array_merge)成一个数组,再根据数据的创建时间降序排序取前4条。 遇到这个...2014-06-07
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了C#实现字符串转换成字节数组的简单实现方法,仅一行代码即可搞定,非常简单实用,需要的朋友可以参考下...2020-06-25