李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构学习--环形队列(二)
Leefs
2020-01-26 PM
1750℃
0条
# 数据结构学习--环形队列(二) ### 前言 上篇中,使用数组来模拟队列会出现数组使用一次就不能使用,没有达到复用效果的问题,本篇通过数组**模拟环形队列**来解决该问题。 ### 概述 **数组模拟环形队列** 对前面的数组模拟队列的优化,充分利用数据,因此将数组看做是一个环形的。(通过取模的方式来实现即可) **分析说明:** > 1. 尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意`(rear+1)%maxSize==front` [满] > > 2. rear==front[空] **分析示意图:** ![02.队列01.png][1] **思路如下:** > 1. front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值等于0. > > 2. rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定,rear的初始值等于0 > 3. 当队列满时,条件是`(rear+1)%maxSize==front`【满】 > 4. 当队列为空时,rear==front【空】 > 5. 队列中有效的数据的个数:`(rear+maxSize-front)%maxSize` //rear=1 front=0 在原来的队列上修改得到一个环形队列。 **代码** ```java public class CircleArrayQueueDemo { public static void main(String[] args) { //创建一个队列 CircleArray queue= new CircleArray(4);//说明:设置4,其队列的有效 数据最大是3 char key=' ';//接收用户输入 Scanner scanner = new Scanner(System.in); boolean loop = true; //输出一个菜单 while(loop){ System.out.println("s(show):显示队列"); System.out.println("e(exit):退出程序"); System.out.println("a(add):添加数据到队列"); System.out.println("g(get):从队列取出数据"); System.out.println("h(head):查看队列头的数据"); key = scanner.next().charAt(0);//接收一个字符 switch (key){ case 's': queue.showQueue(); break; case 'a': System.out.println("输出一个数"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g'://取出数据 try{ int res = queue.getQueue(); System.out.printf("取出的数据是%d\n",res); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'h'://查看队列头的数据 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n",res); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 'e'://退出 scanner.close(); loop=false; break; default: break; } } System.out.println("程序退出!"); } } class CircleArray{ private int maxSize;//表示数组的最大容量 //front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一个元素front的初始值等于0. private int front;//对列头 //rear变量的含义做一个调整:rear指向队列的最后一个元素的后一个位置。因为希望空出一个空间做为约定,rear的初始值等于0 private int rear;//队列尾 private int[] arr;//该数据用于存放数据,模拟队列 public CircleArray(int arrMaxSize){ maxSize = arrMaxSize; arr = new int[maxSize]; } //判断队列是否满 public boolean isFull(){ return (rear+1)%maxSize == front; } //判断队列是否为空 public boolean isEmpty(){ return rear == front; } //添加数据到队列 public void addQueue(int n){ //判断队列是否满 if(isFull()){ System.out.println("队列满,不能加入数据!"); return; } //直接将数据加入 arr[rear]=n; //将 rear 后移,这里必须考虑取模 rear = (rear +1)%maxSize; } //获取队列的数据,出队列 public int getQueue(){ //判断队列是否空 if(isEmpty()){ //通过抛出异常 throw new RuntimeException("队列空,不能取数据"); } //这里需要分析出front是指向队列的第一个元素 //1.先把front对应的值保留到一个临时变量 //2. 将front后移,考虑取模 //3. 将临时保存的变量返回 int value = arr[front]; front = (front + 1)%maxSize; return value; } //显示队列的所有数据 public void showQueue(){ //遍历 if(isEmpty()){ System.out.println("队列为空,没有数据"); return; } //思路:从front开始遍历,遍历多少个元素 for(int i=front;i
标签:
队列
,
数据结构
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://www.lilinchao.com/archives/473.html
上一篇
数据结构学习--队列(一)
下一篇
数据结构学习--链表
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
47
标签云
SpringBoot
Spark Core
设计模式
JavaWeb
Linux
序列化和反序列化
Java
锁
正则表达式
Git
链表
稀疏数组
Sentinel
Spark Streaming
国产数据库改造
Flink
微服务
JavaSE
JavaWEB项目搭建
Docker
Azkaban
散列
Kafka
JVM
Redis
Nacos
nginx
Http
ClickHouse
Golang
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞