队列：队列是一个有序列表，可以用数组或是链表来实现。
原则：队列遵循先入先出的原则，即先存入队列的数据要先取出，后存入的数据后取出。
数组模拟队列：
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下，其中maxSize是该队列的最大容量。又因为队列的输入、输出是分别从前后端来处理的，因此还需要两个变量 front 和 rear 分别记录队列前后端的下标。其中，front 会随着数据输出而改变，而 rear随着数组的输入而改变。
数组模拟队列思路分析：
关键：入队列——addQueue
1）将尾指针向后移，rear+1，当 front = rear时为空队列；
2）若尾指针rear小于队列的最大小标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。当 rear = maxSize 时为满队列。
代码实现：
package queue;
import java.util.Scanner;
public class arrayToQueue {
public static void main(String[] args) {
//测试队列
ArrayQueue queue = new ArrayQueue(3);
Scanner input = new Scanner(System.in);
boolean loop = true;
while (loop){
System.out.println("=========菜单=========");
System.out.println("s(show):显示队列");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
System.out.println("e(exit):退出程序");
char key = input.next().charAt(0);
switch (key){
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("请输入添加的数据：");
int data = input.nextInt();
queue.addQueue(data);
break;
case 'g':
try {
int res = queue.getQueue();
System.out.println("取出的数据是："+res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = queue.headQueue();
System.out.println("队列头的数据是："+head);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
input.close();
loop = false;
break;
default:
break;
}
}
System.out.println("退出程序！");
}
}
//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue {
int maxSize;//表示数组的最大容量
int[] array;//新建数组用于存放数据
int front;//队列头
int rear;//队列尾
//创建队列的构造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
array = new int[maxSize];
front = -1;//指向队列头部，不包含数据
rear = -1;//指向队列尾部，包含数据
}
//判断队列是否满
public boolean isFull() {
return rear == maxSize - 1;
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//添加数据到队列，即入队列
public void addQueue(int data) {
//判断队列是否满
if (isFull()) {
System.out.println("队列已满，不能添加数据！");
return;
}
rear++;
array[rear] = data;
}
//获取队列的数据，即出队列
public int getQueue() {
//判断队列是否为空
if (isEmpty()) {
//return -1;避免产生获取的数据为-1的误会，通过抛出异常处理
throw new RuntimeException("队列为空，没有可查询的数据！");
}
front++;
return array[front];
}
//显示队列所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列是空的，没有可以显示的数据！");
return;
}
for (int i = front + 1; i < rear + 1; i++) {
System.out.printf("array[%d] = %d\n", i, array[i]);
}
}
public int headQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有可查询的数据！");
}
return array[front+1];
}
}
问题分析并优化
1）目前数组使用一次就不能用，没有达到复用的效果；
2）将这个数组使用算法，改进成为一个环形的队列。
数组模拟环形队列的思路分析：
1）?front?变量含义的调整：?front?指向队列的第一个元素，也就是说?array[front]?就是队列的第一个元素，front的初始值为0；
2）rear?变量含义的调整：?rear?指向队列的最后一个元素的后一个位置，空出一个空间便于做环形约定，rear 的初始值为0；
3）约定：当队列满时，条件是（rear+1）%maxSize = front ；
4）约定：当队列为空时，条件是?rear =?front；
5）队伍中有效数据的个数是：（rear+maxSize-front）%maxSize；
代码实现：
package circleQueue;
import java.util.Scanner;
public class circle_queue {
public static void main(String[] args) {
//测试循环队列
CircleQueue circlequeue = new CircleQueue(4);//有效数据最大是3
Scanner input = new Scanner(System.in);
boolean loop = true;
while (loop){
System.out.println("=========菜单=========");
System.out.println("s(show):显示队列");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列取出数据");
System.out.println("h(head):查看队列头的数据");
System.out.println("e(exit):退出程序");
char key = input.next().charAt(0);
switch (key){
case 's':
circlequeue.showQueue();
break;
case 'a':
System.out.println("请输入添加的数据：");
int data = input.nextInt();
circlequeue.addQueue(data);
break;
case 'g':
try {
int res = circlequeue.getQueue();
System.out.println("取出的数据是："+res);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int head = circlequeue.headQueue();
System.out.println("队列头的数据是："+head);
}catch (Exception e){
System.out.println(e.getMessage());
}
break;
case 'e':
input.close();
loop = false;
break;
default:
break;
}
}
System.out.println("退出程序！");
}
}
class CircleQueue{
private int maxSize;
private int front;
private int rear;
private int[] array;
public CircleQueue(int arrMaxSize){
maxSize = arrMaxSize;
array = new int[maxSize];
//front rear 默认值为0
}
//判断队列是否满
public boolean isFull() {
return (rear+1)%maxSize == front;
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//添加数据到队列，即入队列
public void addQueue(int data) {
//判断队列是否满
if (isFull()) {
System.out.println("队列已满，不能添加数据！");
return;
}
//直接将数据加入
array[rear] = data;
rear = (rear+1)%maxSize;//循环
}
//获取队列的数据，即出队列
public int getQueue() {
//判断队列是否为空
if (isEmpty()) {
//return -1;避免产生获取的数据为-1的误会，通过抛出异常处理
throw new RuntimeException("队列为空，没有可查询的数据！");
}
int temp = array[front];
front = (front+1)%maxSize;//循环
return temp;
}
//显示队列所有数据
public void showQueue() {
if (isEmpty()) {
System.out.println("队列是空的，没有可以显示的数据！");
return;
}
for (int i = front; i < front+vaildSize(); i++) {
System.out.printf("array[%d] = %d\n", i%maxSize, array[i%maxSize]);
}
}
//有效数据个数
public int vaildSize(){
return (rear+maxSize-front)%maxSize;
}
public int headQueue(){
if (isEmpty()){
throw new RuntimeException("队列为空，没有可查询的数据！");
}
return array[front];
}
}
