队列介绍
队列是一个有序列表，可以用数组或是链表来实现。 遵循先入先出的原则。
即：先存入队列的数据，要先取出。后存入的要后取出 示意图：(使用数组模拟队列示意图)
数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，
如图所示:
当我们将数据存入队列时称为”addQueue”，
addQueue 的处理需要有两个步骤：
思路分析 将尾指针往后移：
rear+1 , 当front == rear 【空】 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。
rear == maxSize - 1[队列满] 代码实现 问题分析并优化
代码实现
package com.lin.queue_0131;
import java.util.Scanner;
public class Array_Queue {
public static void main(String[] args) {
ArrayQueue arrayQueue = new ArrayQueue(4);
Scanner scanner = new Scanner(System.in);
char c;
while(true) {
System.out.println("------------------------------");
System.out.println("|");
System.out.println("|");
System.out.println("------------------------------");
System.out.println("-1 s(show):显示队列, -2 e(exit)：退出程序, -3 a(add)：添加数据到队列, -4 g(get)：获取队列的数据, -5 h(head):查看队列头数据 ");
System.out.println("请输入以上提示字符：");
c = scanner.next().charAt(0);
switch (c) {
case 's':
arrayQueue.showQueue();
break;
case 'e':
System.exit(0);
break;
case 'a':
System.out.println("请输入添加数据：");
int n = scanner.nextInt();
arrayQueue.addQueue(n);
break;
case 'g':
try {
System.out.println("出队：" + arrayQueue.getQueue());
} catch (NullQueueException e) {
System.err.println(e.getMessage());
}
break;
case 'h':
try {
System.out.println("头数据：" + arrayQueue.headQueue());
} catch (NullQueueException e) {
System.err.println(e.getMessage());
}
break;
default:
break;
}
}
}
}
class ArrayQueue{
private int fornt;
private int rear;
private int maxSize;
private int[] arr;
// 创建队列构造器
public ArrayQueue(int maxSize){
this.arr = new int[maxSize];
this.maxSize = maxSize;
this.rear = -1; // 指向队尾的数据
this.fornt = -1; // 指向队列头的前一位置
}
// 判断队列是否已满
public boolean isFull() {
return rear == (maxSize - 1);
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == fornt;
}
// 入队
public void addQueue(int n) {
if(!isFull()) {
arr[++rear] = n;
System.out.println("添加成功！");
} else {
System.out.println("队列已满！");
}
}
// 出队
public int getQueue() throws NullQueueException {
if(isEmpty()) {
throw new NullQueueException("队列为空！"); // 自定义异常
}
int arrNum = arr[++fornt];
arr[fornt] = 0;
return arrNum;
}
// 遍历队列
public void showQueue() {
if(isEmpty()) {
System.out.println("队列为空，无法输出数据！");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print("arr[" + i + "] = " + arr[i] + "\t");
}
System.out.println();
}
// 显示队列的头数据
public int headQueue() throws NullQueueException {
if(isEmpty()) {
throw new NullQueueException("队列为空！"); // 自定义异常
}
return arr[fornt +1];
}
}
注意：没有优化的代码数组只能用一次，即使队列为空，也无法添加数据。
优化后的代码
环形队列调整思路（其中的一种办法）：
front变量的含义：front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，之前的front是指向队列头元素的前一个位置。初始值为0。
rear变量的含义：rear指向队列的最后一个元素的后一个位置。希望空出一个空间作为约定。初始值为0。
当队列满时，条件是(rear + 1)%maxSize == front。
当队列为空时，条件是rear == front。
有效个数：(rear + maxSize - front)%maxSize。
package com.lin.queue_0131;
import java.util.Scanner;
public class ArrayQueuePuls {
public static void main(String[] args) {
ArrayQueue2 arrayQueue2 = new ArrayQueue2(4);
Scanner scanner = new Scanner(System.in);
char c;
while(true) {
System.out.println("------------------------------");
System.out.println("|");
System.out.println("|");
System.out.println("------------------------------");
System.out.println("-1 s(show):显示队列, -2 e(exit)：退出程序, -3 a(add)：添加数据到队列, -4 g(get)：获取队列的数据, -5 h(head):查看队列头数据,-1 printFornt,-2 printRear ");
System.out.println("请输入以上提示字符：");
c = scanner.next().charAt(0);
switch (c) {
case 's':
arrayQueue2.showQueue();
break;
case 'e':
System.exit(0);
break;
case 'a':
System.out.println("请输入添加数据：");
int n = scanner.nextInt();
arrayQueue2.addQueue(n);
break;
case 'g':
try {
System.out.println("出队：" + arrayQueue2.getQueue());
} catch (NullQueueException e) {
System.err.println(e.getMessage());
}
break;
case 'h':
try {
System.out.println("头数据：" + arrayQueue2.headQueue());
} catch (NullQueueException e) {
System.err.println(e.getMessage());
}
break;
case '1':
arrayQueue2.printFront();
break;
case '2':
arrayQueue2.printRear();
break;
default:
break;
}
}
}
}
class ArrayQueue2{
private int fornt;
private int rear;
private int maxSize;
private int[] arr;
// 创建队列构造器
public ArrayQueue2(int maxSize){
this.arr = new int[maxSize];
this.maxSize = maxSize;
this.rear = 0; // 指向队尾的数据
this.fornt = 0; // 指向队列头的前一位置
}
// 判断队列是否已满
public boolean isFull() {
return (rear + 1)%maxSize == fornt;
}
// 判断队列是否为空
public boolean isEmpty() {
return rear == fornt;
}
// 入队
public void addQueue(int n) {
if(!isFull()) {
arr[rear] = n;
rear = (rear + 1)%maxSize;
System.out.println("添加成功！");
} else {
System.out.println("队列已满！");
}
}
// 出队
public int getQueue() throws NullQueueException {
if(isEmpty()) {
throw new NullQueueException("队列为空！"); // 自定义异常
}
int arrNum = arr[fornt];
fornt = (fornt + 1)%maxSize;
return arrNum;
}
// 遍历队列
public void showQueue() {
if(isEmpty()) {
System.out.println("队列为空，无法输出数据！");
return;
}
for (int i = fornt; i < fornt + numSize(); i++) {
System.out.print("arr[" + i%maxSize + "] = " + arr[i%maxSize] + "\t");
}
System.out.println();
}
public int numSize() {
return (rear + maxSize - fornt)%maxSize; // (rear + maxSize - fornt)%maxSize环形队列元素的实际个数
}
// 显示队列的头数据
public int headQueue() throws NullQueueException {
if(isEmpty()) {
throw new NullQueueException("队列为空！"); // 自定义异常
}
return arr[fornt];
}
public void printFront() {
System.out.println(this.fornt);
}
public void printRear() {
System.out.println(this.rear);
}
}
虽然数组size为4，但容量只有3
最后，fornt单词写错了，应该是front。
仅供参考，有错误还请指出！
有什么想法，评论区留言，互相指教指教。