package com.ws.队列.数组环形队列;
//环形数组队列
//判断满:尾+1%队列长度==头
//添加数据:要(尾+1)%数组长度
//取出数据:要(头+1)%数组长度 因为这两个都是循环的,相当于一个圆环,%数组长度就是转圈
//队列有效数据个数:(尾+数组长度-头)%数组长度 数组因为是个圈,所以可能出现头>尾的情况,所以要提前转一圈,保证尾>头
//取数据:i%数组长度
//因为到最后一个时判断空是尾+1然后取余,实际数组最后一个空间存不上,所以实际的有效队列长度是maxSize-1
import java.util.Scanner;
public class ArrayQueue {
public static void main(String[] args) {
//测试
Array array=new Array(3);
char key=' ';//接收用户输入
Scanner scanner=new Scanner(System.in);
boolean loop=true;
while (loop){
System.out.println("a:显示队列");
System.out.println("b:退出程序");
System.out.println("c:添加数据到队列");
System.out.println("d:从队列取出数据");
System.out.println("e:显示队列头数据");
key=scanner.next().charAt(0);//接收一个字符
switch (key){
case 'a':
array.printqueue();
break;
case 'c':
System.out.println("输入一个数");
int value=scanner.nextInt();
array.addArray(value);
break;
case 'd':
try {
int get=array.getArray();
System.out.println("取出的数据是:"+get);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
try {
System.out.println("队列头数据是:"+array.printtou());
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'b':
scanner.close();
loop=false;
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
//使用数组模拟一个队列
class Array{
private int maxSize;//数组最大容量
private int tou;//队列头
private int wei;//队列尾
private int arr[];//数组,存数据
//创建队列构造器
public Array(int maxSize){
this.maxSize=maxSize;
arr=new int[maxSize];
tou=0;//队列头数据
wei=0;//队列尾数据
}
//判断队列是否满
public boolean ifMax(){
return (wei+1)%maxSize==tou;
}
//判断队列是否为空
public boolean ifFull(){
return tou==wei;
}
//添加数据到队列
public void addArray(int queue){
//判断队列是否满
if (ifMax()){
System.out.println("队列满不能添加数据");
return;
}
//直接将数据加入
arr[wei]=queue;
//尾后移,得考虑取模
wei=(wei+1)%maxSize;
}
//出队列
public int getArray(){
//判断队列是否为空
if (ifFull()){
//抛出异常
throw new RuntimeException("队列为空!不能取数据");
}
//指向队列第一个元素
int value=arr[tou];
tou=(tou+1)%maxSize;
return value;
}
//显示队列的所有数据
public void printqueue(){
if (ifFull()){
System.out.println("队列为空,没有数据");
return;
}
//从头开始遍历,遍历有效数据个数
for (int i=tou;i<tou+size();i++){
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
//求出当前队列有效数据个数
public int size(){
return (wei+maxSize-tou)%maxSize;//就是转圈
}
//显示队列的头是
public int printtou(){
//判断队列空
if (ifFull()){
throw new RuntimeException("队列空,无头数据");
}
return arr[tou];
}
}