Java队列篇之实现数组模拟队列及可复用环形队列详解
作者：叶绿体不忘呼吸 发布时间：2021-09-12 17:49:42
标签：Java,队列,数组模拟队列,可复用环形队列
队列简介
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即先存入队列的数据，先取出，后存入的后取出。
示意图：(使用数组模拟队列示意图)
有两个分别指向头部和尾部的“指针”。
数组模拟队列（无法复用）
1、实现思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：
当我们将数据存入队列时称为addQueue，addQueue的处理需要有两个步骤：
①将尾指针往后移。
②若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear 所指的数组元素中，否则无法存入数据。
rear+1当front== rear[空]
rear==maxSize-1[队列满]
2、代码实现
①数组实现队列类
class ArrQueue {
private int maxSize; //队列（数组）最大容量
private int front; //指向队列头部
private int rear; //指向队列尾部
private int[] queue;
//创造队列的构造器
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new int[maxSize];
front = -1; //其实是队列第一个元素的前一个索引
rear = -1; //最后一个元素的索引
}
//判断是否满
public boolean isFull(){
return rear == maxSize - 1;
}
//判断是否空
public boolean isEmpty(){
return front == rear;
}
//添加元素
public void addQueue(int n){
if (isFull()){
System.out.println("队列已经满了，无法添加！");
return;
}else {
rear++;
queue[rear] = n;
}
}
//取出元素
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，无元素可取！");
}else {
front++;
return queue[front];
}
}
//显示队列
public void showQueue(){
if (isEmpty()){
System.out.println("队列为空，没有元素可显示！");
return;
}
for (int i : queue){
System.out.println(i);
}
}
//显示头数据
public void headQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有头数据！");
}
int i = front;
System.out.println(queue[++i]);
}
}
②测试类
import java.util.Scanner;
/**
* @Author: Yeman
* @Date: 2021-10-11-22:02
* @Description:
*/
public class ArrayQueueTest {
public static void main(String[] args) {
//创建一个队列
ArrQueue arrQueue = new ArrQueue(3);
//创建一个用户输入
Scanner scanner = new Scanner(System.in);
//创建一个功能菜单
char key = ' ';
boolean isShow = true;
while (isShow){
System.out.println("s:显示队列");
System.out.println("a:添加数据");
System.out.println("g:取出数据");
System.out.println("h:显示头数据");
System.out.println("e:退出程序");
key = scanner.next().charAt(0);
switch (key){
case 's' :
arrQueue.showQueue();
break;
case 'a' :
System.out.println("请输入一个数：");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g' :
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h' :
try {
arrQueue.headQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e' :
isShow = false;
break;
}
}
System.out.println("程序退出...");
}
}
数组模拟环形队列（可复用）
对前面的数组模拟队列的优化，充分利用数组。将数组看做是一个环形的，即取出之后，有位置可以空出来添加。(通过取模的方式来实现即可)
分析说明:
①尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定。在作判断队列满的时候需要注意(rear+ 1) ％ maxSize== front [满]
②rear == front [空]
1、思路如下:
①front 变量的含义调整：front 指向队列的第一个元素, 也就是说arr[front]就是队列的第一个元素，front的初始值为0。
②rear 变量的含义调整：rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定，rear的初始值=0。
③当队列满时，条件是(rear + 1) ％ maxSize == front [满]
④对队列为空的条件是rear== front[空]
⑤当我们这样分析，队列中有效的数据的个数(rear + maxSize - front) ％ maxSize
⑥我们就可以在原来的队列上修改得到一个环形队列
2、代码实现
①数组实现环形队列类
class ArrQueue {
private int maxSize; //队列（数组）最大容量
private int front; //指向队列头部，队列第一个元素的索引
private int rear; //指向队列尾部，队列最后一个元素的后一个索引
private int[] queue;
//创造队列的构造器
public ArrQueue(int maxSize){
this.maxSize = maxSize;
queue = new int[maxSize];
}
//判断是否满
public boolean isFull(){
return (rear + 1) ％ maxSize == front;
}
//判断是否空
public boolean isEmpty(){
return front == rear;
}
//添加元素
public void addQueue(int n){
if (isFull()){
System.out.println("队列已经满了，无法添加！");
return;
}else {
queue[rear] = n;
rear = (rear + 1) ％ maxSize;
}
}
//取出元素
public int getQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，无元素可取！");
}else {
int data = queue[front];
front = (front + 1) ％ maxSize;
return data;
}
}
//显示队列
public void showQueue(){
if (isEmpty()){
System.out.println("队列为空，没有元素可显示！");
return;
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[％d] = ％d\n",i ％ maxSize,queue[i ％ maxSize]);
}
}
//求当前队列有效数据个数
public int size(){
return (rear + maxSize - front) ％ maxSize;
}
//显示头数据
public void headQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有头数据！");
}
System.out.println(queue[front]);
}
}
②测试类
import java.util.Scanner;
/**
* @Author: Yeman
* @Date: 2021-10-11-22:02
* @Description:
*/
public class ArrayQueueTest {
public static void main(String[] args) {
//创建一个队列
ArrQueue arrQueue = new ArrQueue(3); //说明该环形队列的最大有效数据为2
//创建一个用户输入
Scanner scanner = new Scanner(System.in);
//创建一个功能菜单
char key = ' ';
boolean isShow = true;
while (isShow){
System.out.println("s:显示队列");
System.out.println("a:添加数据");
System.out.println("g:取出数据");
System.out.println("h:显示头数据");
System.out.println("e:退出程序");
key = scanner.next().charAt(0);
switch (key){
case 's' :
arrQueue.showQueue();
break;
case 'a' :
System.out.println("请输入一个数：");
int value = scanner.nextInt();
arrQueue.addQueue(value);
break;
case 'g' :
try {
System.out.println(arrQueue.getQueue());
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h' :
try {
arrQueue.headQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e' :
isShow = false;
break;
}
}
System.out.println("程序退出...");
}
}
来源：https://blog.csdn.net/m0_46653805/article/details/120712729
0
投稿猜你喜欢
- 今天碰到一个很坑的问题，折腾了五六个小时，网上也收不到答案，国外有哥们碰到了，但是看到有解决方法的回复，废话不多说了。现象：运行maven
- /* * Copyright 2012-2013 The Haohui Network Cor
- spring容器是负责实例化、配置、组装组件的容器。容器的配置有很多，常用的是xml、Java注解和Java代码。在spring中Ioc容器
- 先来一个常见的错误信息：Due to limitations of the com.mongodb.BasicDocument, you c
- 本文实例讲述了C#检测远程计算机端口是否打开的方法。分享给大家供大家参考。具体分析如下：这段C#代码用于检测远程计算机的3389端口是否处理
其实这个比较简单，子线程怎么通知主线程，就是让子线程做完了自己的事儿就去干主线程的转回去干主线程的事儿。那么怎么让子线程去做主线程的事儿呢，- 本文实例讲述了C#实现的上传图片、保存图片、加水印、生成缩略图功能。分享给大家供大家参考，具体如下：伴随移动设备地普及，处理图片、视频等需求
- 这里简单介绍一下ZXing库。ZXing是一个开放源码的，用Java实现的多种格式的1D/2D条码图像处理库，它包含了联系到其他语言的端口。
- 一、Optional类的出现到目前为止，臭名昭著的空指针异常是导致Java应用程序失败的最常见原因。以前，为了解决空指针异常，Google公
- 一、前言(吐槽+煽情+简介) &n
- 一、Monkey 是什么？Monkey 就是SDK中附带的一个工具。二、Monkey 测试的目的？:该工具用于进行压力测试。 然后开发人员结
- 可以使用System.ServiceProcess.ServiceController这个类允许连接到正在运行或者已停止的服务、对其进行操作
- 项目中出了个 BUG，就在我眼皮子底下，很明显的一个 BUG，愣是看了两天才看出来。我有多个任务并发，任务执行完成后都有一个返回结果，我用一
- GitHub有一个开源控件PickerView，可以实现 * 联动的效果。虽然该控件使用非常简单，但是填充数据异常繁琐。GitHub上的Dem
- 本文实例讲述了android中ListView数据刷新时的同步方法。分享给大家供大家参考。具体实现方法如下：public class Mai
- 面对android studio Run 一次项目要等好几分钟的痛点，不得不研究一下android studio 的单元测试。其实我的目的很
- Java HashSetHashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。HashSet 允许有 null 值。
- 归并排序算法思想:分而治之(divide - conquer);每个递归过程涉及三个步骤第一, 分解: 把待排序的 n 个元素的序列分解成两
- 前面讲述了使用POI导出Word文件和读取Excel文件，这两个例子都相对简单，接下来要讲述的使用POI导出Excel文件要复杂得多，内容也
- 1.MyBatis动态SQLMyBatis 的强大特性之一便是它的动态 SQL，即拼接SQL字符串。如果你有使用 JDBC 或其他类似框架的
