Java数组模拟队列
简介
本文主要内容在Java代码中用数组模拟一个队列出来，这里只简要一提，不过多的介绍队列基本概念
队列是一种特殊的线性表，特点是先进先出。
和栈相似，它们的操作都是受限的。
这里要说的队列，只有两种操作，插入一个数据称为入队，删除一个数据称为出队，并且只能从队尾插入数据，只能在队头删除数据。
队列的数组实现
从百度百科中可以看到对队列的描述
简要来说，实现一个队列，本质上需要一片连续的存储空间，可以是静态分配，也可以动态申请
数组呢，正好就可以贴合这个要求，静态分配一段定长的连续内存空间
除此之外，还需要两个指针，一个指向队头，一个指向队尾
入队操作是在队尾添加数据，所以要在指向队尾的指针后一个位置添加数据，并且将指针指向新的队尾，也就是尾指针后移
出队操作是取出并删除队头的数据，其实删除数据的操作，就是在指向队头的指针处取得数据返回，然后将队头指针后移即可
我们发现，在操作数据的同时，需要伴随着指针的移动
分析一把，如果将头指针正好指向当前队头，尾指针正好指向当前队尾
注意：完整实现一个队列，需要有入队、出队、初始化三个操作。但用数组实现队列，因为存储空间是静态分配的定长空间，意味着队列容量有最大值，所以还需要判断队列满和队列空两种情况
1.入队：将尾指针后移一下，然后，将数据放到尾指针位置；（需要先判断队列是否还没满）
2.出队：将头指针位置的数据取出，然后，后移头指针；（需要先判断是否有数据可以出队）
3.判断队列的空满问题：
这种方式下，在操作出入队之前，尾指针正好指向队尾，头指针正好指向队头
所以，尾指针数值 - 头指针数值 +1 = 当前队列数据量，我们判断这个计算出的当前队列数据量，如果等于最大容量就说明队列满了，如果等于0就说明队列是空的
4.初始化队列：
初始化队列时，首先分析初始化的队列是空的，根据判断队列为空的方式，发现，当队列空时，头指针在尾指针的后一个位置；再分析第一个入队的数据要放在数组的第一个位置，也就是索引0的位置，而入队时先将尾指针后移，再将数据放在尾指针位置，所以初始化尾指针要指向-1；而头指针要在尾指针后一位，也就是初始化头指针指向0。
5.改进：
这样的方式实现队列后，会发现指针一直在后移，添加到最大容量后，指针就会超出边界，即便数据都已经出列了，也无法再入队，所以其实当指针移动到最大容量位置时，再向后移应该是移动到第一个，让队列首尾相连变成一个环状
实现这个的方式是，每次在移动指针后进行一次（指针%最大容量）的取余运算
但这样会出现问题，原先的计算当前数据量公式就不再正确，还需要将（结果%最大容量）进行取余运算
也可以放任指针持续后移，在取数据和插入数据的时候对指针取余，这样不影响计算数据量公式
实现方式其实并不唯一，取决于你对头尾指针的设定
下面的代码演示中，设定为：头指针指向队列头的前一个数据，尾指针指向队列尾
区别就是：
1.判断队列容量：尾指针-头指针正好等于队列容量，不需要加一
2.入队出队操作都是先移动指针，再操作数据
眼观千遍，不如手动一遍
读者朋友可以看完我的实现代码后，自行根据上面分析与代码不同的思路实现一遍，当做一个小练习
class ArrayQueueEntity{
/**
* 数组最大容量
*/
private final int maxSize;
/**
* 约定指向队列头的前一个位置
*/
private int front;
/**
* 指向队列尾
*/
private int rear;
/**
* 模拟队列用于存放数据的数组
*/
private final int[] arr;
/**
* 构造器，创建队列(初始化队列)
* @param arrMaxSize 队列最大容量
*/
public ArrayQueueEntity(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
//初始化时头指针指向第一个数据的前一个（其实表示这个位置是上一次出列的数据位置）
front = -1;
//初始化时尾指针需要指向当前最后一个数据的索引，但初始化队列为空找不到队尾，所以根据空队列判断尾指针-头指针=0，设置为-1
rear = -1;
}
/**
* 判断队列是否是满的
* @return true表示队列满了，false表示队列没满
*/
public boolean isFull(){
return rear - front >= maxSize;
}
/**
* 判断队列是否为空
* @return true表示为空，false表示不为空
*/
public boolean isEmpty(){
return rear - front == 0;
}
/**
* 添加数据到队列
* @param data 要添加的数据
*/
public void addQueue(int data){
//判断队列是否已满
if (!isFull()){
//队列没满，添加数据
//队列尾指针后移
rear++;
//在尾指针处添加数据(指针位置都一直在后移，所以要对数组容量取余，模拟成环形队列)
arr[rear%maxSize] = data;
}else {
//队列满了输出提示
System.out.println("队列满，不能加入数据");
}
}
/**
* 获取队列数据/出队列
* @return 出队列的数据
*/
public int getQueue(){
//先判断队列是否为空
if (isEmpty()){
throw new RuntimeException("队列为空");
}
//不为空，取数据
//头指针后移一下，指向需要出列的数据
front++;
//让指针位置数据出列即可
return arr[front%maxSize];
}
/**
* 打印当前队列的所有数据
*/
public void printQueue(){
System.out.println("正在打印当前队列......");
//先判断队列是否为空
if (!isEmpty()){
//不为空就遍历打印，从头指针的下一个遍历到尾指针
for (int i = front+1; i <= rear; i++) {
System.out.println(i+":"+arr[i%maxSize]);
}
}else {
System.out.println("队列中没有数据");
}
}
}
模拟上面代码，完成小练习后，可以用下面这个主方法来测试一下队列
public static void main(String[] args) {
//初始化队列——最大容量为3
ArrayQueueEntity queue = new ArrayQueueEntity(3);
//接收用户输入
String 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):从队列取出数据");
key = scanner.next();
switch (key){
case "s":
queue.printQueue();
break;
case "e":
loop=false;
break;
case "a":
if (queue.isFull()){
System.out.println("队列已满，清先出列一些数据再试");
break;
}
System.out.println("请输入要入队的数字：");
int data = scanner.nextInt();
queue.addQueue(data);
break;
case "g":
if (queue.isEmpty()){
System.out.println("队列为空，没有数据可以出列，请先尝试添加数据入列");
break;
}
System.out.println("出列成功，出列数据为："+queue.getQueue());
break;
default:
System.out.println("请根据菜单提示输入正确指令");
}
}
}
