文章目录
队列
队列的使用场景
队列介绍
- 队列是一个有序列表，可以用数组或者是链表来实现
- 遵循先入先出的原则。即：现存入队列的数据，要先取出。后存入的要后取出。
-
示意图：（使用数组模拟队列示意图）
数组模拟队列
- 队列本身是有序列表，若使用数组的结构来存队列的数据，则队列数组的声明如上图，其中的maxSize是该队列的最大容量。
- 因为队列的输出，输入是分别从前后端来处理的，因此需要两个变量==front==及==rear==分别记录队列前后端的下标，front会随着数据的输出而改变，而rear则是随着数据输入而改变，如上图所示：
- 当我们将数据存入队列时称为 "addQueue ",addQueue的处理需要有两个步骤：
思路分析
1）将尾指针往后移：rear+1，当front=rear 【空】
2）若尾指针rear 小于队列的最大下标 maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear==maxSize-1； 【队列满】
代码实现
package com.atguigu.queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//测试一把
//初始化创建一个队列
ArrayQueue queue = 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'://显示队列
queue.showQueue();
break;
case 'a'://添加数据
System.out.println("请输入一个数字");
int value=scanner.nextInt();
queue.addQueue(value);
break;
case 'g'://取出数据 try catch 异常捕获
try{
int res=queue.getQueue();
System.out.printf("取出的数据是%d\n",res);
}catch(Exception e){
//TODO :handle exception
System.out.println(e.getMessage());
}
break;
case 'h'://查看队列头的数据是什么
try{
int res=queue.headQueue();
System.out.printf("队列头的数据是%d\n",res);
}catch(Exception e){
//TODO :handle exception
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop=false;
break;
default:
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;//指向队列头部，分析出front是指向队列头的前一个位置
rear=-1;//指向队列尾，指向队列为的数据，（即就是队列的最后一个数据）
}
// 判断队列是否满
public boolean isFull(){
return rear==maxSize-1;
}
// 判断队列是否是空
public boolean isEmpty(){
return rear==front;
}
// 添加数据到队列
public void addQueue(int n){
// 判断队列是否已满
if(isFull()){
System.out.println("队列满，不能加入数据！！！");
return;
}
rear++;// 让rear 后移
arr[rear]=n;
}
// 获取队列的的数据 ， 出队列
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=front+1;i<rear+1;i++){
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
// 显示队列的头数据，注意不是取出数据
public int headQueue(){
//判断
if(isEmpty()){
throw new RuntimeException("队列空，不能取数据");
}
return arr[front+1];
}
}
运行结果
"D:\Program Files\Java\jdk1.8.0_131\bin\java.exe" "-javaagent:D:\Program
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
队列是空的，没有数据！！！
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
请输入一个数字
10
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
arr[0]=10
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
请输入一个数字
20
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
请输入一个数字
30
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
arr[0]=10
arr[1]=20
arr[2]=30
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
请输入一个数字
40
队列满，不能加入数据！！！
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
h
队列头的数据是10
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
h
队列头的数据是10
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
取出的数据是10
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
h
队列头的数据是20
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
取出的数据是20
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
取出的数据是30
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
g
队列空，不能取数据
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
s
队列是空的，没有数据！！！
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
a
请输入一个数字
50
队列满，不能加入数据！！！
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据
e
程序退出！！！
进程已结束，退出代码为 0问题分析并优化
1）目前数组使用一次就不能复用了，没有达到复用的效果
2）将这个数组使用算法，改进成一个环形数组 取模的方式实现的?? %? ??
