java数据结构与算法数组模拟队列示例详解
作者:把苹果咬哭的测试笔记 发布时间:2021-07-23 16:50:24
标签:java,数据结构,算法,队列
一、什么是队列
队列是一个有序列表,可以用数组或者链表来实现。
遵循先入先出的原则,即:先存入队列的数据,要先取出。后存入的的数据,后取出。
看一张队列的模拟图,1,2,3表示同一个队列Queue。在队列中有2个指针,front表示队首,rear表示队尾。
图1中表示队列里还没有数据,所以front跟rear初始化都是-1。
当图2中有数据进行存入的时候,front没变,而rear则随着数据的增多而改变。存入了4个数据,于是rear=3。
再看图3,front变成了2,rear没有变化,因为前面的2个数据被依次先取出,所以队首就变成了2。
这就是队列的“先进先出”了。
二、用数组来模拟队列
思路也比较简单,因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front以及rear分别记录队列的前后端下标。
front会随着数据输出而改变,而rear则是随着数据的输入而改变。
package sparsearray;
import java.util.Scanner;
public class MyArrayQueue {
public static void main(String[] args) {
// 创建一个队列
ArrayQueue arrayQueue = new ArrayQueue(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':
arrayQueue.showQueue();
break;
case 'a':
System.out.println("请要添加的数");
int value = scanner.nextInt();
arrayQueue.addQueue(value);
break;
case 'g':
try {
int res = arrayQueue.getQueue();
System.out.printf("取出的数据是:%d", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int headValue = arrayQueue.showHeadQueue();
System.out.printf("队首数据是:%d", headValue);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
}
}
System.out.println("退出程序");
}
}
// 把队列抽象成一个类,ArrayQueue
class ArrayQueue {
//表示数组最大容量
private int maxSize;
// 队列头
private int front;
// 队列尾
private int rear;
// 用于存放数据的数组
private int[] arr;
// 构造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; // 指向队首的前一个位置
rear = -1; // 指向队列尾部,包括队列最后的这个数据
}
// 判断队列是否已经存满
public boolean isFull() {
return rear == maxSize - 1; // 注意这里的 maxSize-1 为什么要减1
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
// 添加数据到队列
public void addQueue(int num) {
// 判断队列是否满了
if (isFull()) {
System.out.println("队列已满,不可加入数据");
return;
}
rear++; // 让rear后移
arr[rear] = num;
}
// 拿出队列数据
public int getQueue() {
// 判断队列是否空
if (isEmpty()) {
// 抛出异常
throw new RuntimeException("队列为空,不可取数据");
}
front++; // front后移
return arr[front];
}
// 显示队列所有数据
public void showQueue() {
// 遍历
if (isEmpty()) {
System.out.println("队列为空");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// 显示队里的队首数据
public int showHeadQueue() {
if (isEmpty()) {
// 抛出异常
throw new RuntimeException("队列为空,不可取数据");
}
return arr[front + 1]; // 注意这里为甚么要+1,因为指向队首的前一个位置
}
}
可以用代码分别的进行各项操作,看起来似乎没问题。
但是,实际是有问题。
这里创建的数组使用一次就不能接着用了,比如把数据取完后,再往里加数据就不行了。
所以要对其进行优化,使用算法,将其改成一个环形队列,以上就是java数据结构与算法数组模拟队列示例的详解内容,更多关于java数据结构算法数组模拟队列的资料请关注脚本之家其它相关文章!
来源:https://www.cnblogs.com/pingguo-softwaretesting/p/14509117.html
0
投稿
猜你喜欢
- 补充使用Spring Cloud Config加密功能需要下载JCE扩展,用于生成无限长度的密文。链接:http://www.oracle.
- 本文实例为大家分享了UnityShader实现运动模糊的具体代码,供大家参考,具体内容如下原理:像素的当前帧的NDC坐标(x,y
- Springboot启动不检查JPA的数据源配置1.问题有时我们使用spring boot ,在依赖中配置了spring data jpa的
- java读取文件内容,解析Json格式数据一、读取txt文件内容(Json格式数据) public static
- 利用 Spring 工厂加载机制,实例化 ApplicationListener 实现类,并排序对象集合创建应用事件 * 创建类实现接口Ap
- 前言在使用maven配置Mybatis generator插件时报以下错误,generator插件一直无法使用,查询资料说和eclipse版
- 在做项目时,需要一个定时任务来接收数据存入数据库,后端再写一个接口来提供该该数据的最新的那一条。数据保持最新:设计字段sign的值(0,1)
- FFmpeg是一套可以用来记录、转换数字音频、视频,并能将其转化为流的开源计算机程序。采用LGPL或GPL许可证。它提供了录制、转换以及流化
- Android 资源 id详解我们平时获取资源是通过 findViewById 方法进行的,比如我们常在onCreate方法中使用这样的语句
- 缓存是HTTP协议的一个强大功能,但由于某些原因,它主要用于静态资源,如图像,CSS样式表或JavaScript文件,但是,HTTP缓存不仅
- 文章来源:aspcn 作者:孙雯简单的WEB服务器一个简单的WEB服务器将由列表9.2这样构建.当然,还必须要对方法和回应事件进行改进.简单
- 本文介绍的是关于Mybatis中用OGNL表达式处理动态sql的相关内容,分享出来供大家参考学习,下面来一起看看详细的介绍:常用的Mybat
- 在多线程对一个整数进行自增操作时,需要用synchronized进行同步。然而,如果synchronized的对象选取的不合适的话,就无法实
- 原网页:JavaGuideJVM在执行Java程序过程中会把它管理的内存划分成若干个不同的数据区域。JDK1.8和之前的版本略有不同,下面会
- 1、JavaBean介绍 * JavaBean的定义:JavaBeans是Java中一种特殊的类,可以将多个对象封装到一个对象(bean)
- springboot跳转到指定页面controller的写法必须是templates下面的页面,不经过配置,无法直接跳转到public,st
- 前言在讲这两种方式之前,我们先来说明一下什么是java中的jar文件jar (Java Archive File),翻译过来就是java的档
- 前言总结java常见的锁区分各个锁机制以及如何使用使用方法锁名考察线程是否要锁住同步资源乐观锁和悲观锁锁住同步资源后,要不要阻塞不阻塞可以使
- 本节作为主要讲解Spring Data的环境搭建JPA Spring Data :致力于减少数据访问层(DAO)的开发量。开发者唯一要做的就
- 引言一个复杂的分布式系统,用户发起一个请求,这个请求可能调用几十到几百个服务,经过很多业务层,而每个业务又是多个机器集群,一个请求具体被随机