Java队列篇之实现数组模拟队列及可复用环形队列详解

像栈一样，队列（queue）也是一种线性表，它的特性是先进先出，插入在一端，删除在另一端。就像排队一样，刚来的人入队（push）要排在队尾(rear)，每次出队(pop)的都是队首(front)的人队列简介队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出的原则。即先存入队列的数据，先取出，后存入的后取出。示意图：(使用数组模拟队列示意图)

有两个分别指向头部和尾部的“指针”。数组模拟队列（无法复用）1、实现思路队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：

当我们将数据存入队列时称为addQueue，addQueue的处理需要有两个步骤：①将尾指针往后移。②若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear 所指的数组元素中，否则无法存入数据。rear+1当front== rear[空]rear==maxSize-1[队列满]2、代码实现①数组实现队列类12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667class ArrQueue {private int maxSize; //队列（数组）最大容量private int front; //指向队列头部private int rear; //指向队列尾部private int[] queue;//创造队列的构造器public ArrQueue(int maxSize){this.maxSize = maxSize;queue = new int[maxSize];front = -1; //其实是队列第一个元素的前一个索引rear = -1; //最后一个元素的索引}//判断是否满public boolean isFull(){return rear == maxSize - 1;}//判断是否空public boolean isEmpty(){return front == rear;}//添加元素public void addQueue(int n){if (isFull()){System.out.println("队列已经满了，无法添加！");return;}else {rear++;queue[rear] = n;}}//取出元素public int getQueue(){if (isEmpty()){throw new RuntimeException("队列为空，无元素可取！");}else {front++;return queue[front];}}//显示队列public void showQueue(){if (isEmpty()){System.out.println("队列为空，没有元素可显示！");return;}for (int i : queue){System.out.println(i);}}//显示头数据public void headQueue(){if (isEmpty()){throw new RuntimeException("队列为空，没有头数据！");}int i = front;System.out.println(queue[++i]);}}②测试类123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.Scanner;/*** @Author: Yeman* @Date: 2021-10-11-22:02* @Description:*/public class ArrayQueueTest {public static void main(String[] args) {//创建一个队列ArrQueue arrQueue = new ArrQueue(3);//创建一个用户输入Scanner scanner = new Scanner(System.in);//创建一个功能菜单char key = ' ';boolean isShow = true;while (isShow){System.out.println("s:显示队列");System.out.println("a:添加数据");System.out.println("g:取出数据");System.out.println("h:显示头数据");System.out.println("e:退出程序");key = scanner.next().charAt(0);switch (key){case 's' :arrQueue.showQueue();break;case 'a' :System.out.println("请输入一个数：");int value = scanner.nextInt();arrQueue.addQueue(value);break;case 'g' :try {System.out.println(arrQueue.getQueue());} catch (Exception e) {e.printStackTrace();}break;case 'h' :try {arrQueue.headQueue();} catch (Exception e) {e.printStackTrace();}break;case 'e' :isShow = false;break;}}System.out.println("程序退出...");}}数组模拟环形队列（可复用）对前面的数组模拟队列的优化，充分利用数组。将数组看做是一个环形的，即取出之后，有位置可以空出来添加。(通过取模的方式来实现即可)分析说明:①尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定。在作判断队列满的时候需要注意(rear+ 1) % maxSize== front [满]②rear == front [空]1、思路如下:①front 变量的含义调整：front 指向队列的第一个元素, 也就是说arr[front]就是队列的第一个元素，front的初始值为0。②rear 变量的含义调整：rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定，rear的初始值=0。③当队列满时，条件是(rear + 1) % maxSize == front [满]④对队列为空的条件是rear== front[空]⑤当我们这样分析，队列中有效的数据的个数(rear + maxSize - front) % maxSize⑥我们就可以在原来的队列上修改得到一个环形队列2、代码实现①数组实现环形队列类12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970class ArrQueue {private int maxSize; //队列（数组）最大容量private int front; //指向队列头部，队列第一个元素的索引private int rear; //指向队列尾部，队列最后一个元素的后一个索引private int[] queue;//创造队列的构造器public ArrQueue(int maxSize){this.maxSize = maxSize;queue = new int[maxSize];}//判断是否满public boolean isFull(){return (rear + 1) % maxSize == front;}//判断是否空public boolean isEmpty(){return front == rear;}//添加元素public void addQueue(int n){if (isFull()){System.out.println("队列已经满了，无法添加！");return;}else {queue[rear] = n;rear = (rear + 1) % maxSize;}}//取出元素public int getQueue(){if (isEmpty()){throw new RuntimeException("队列为空，无元素可取！");}else {int data = queue[front];front = (front + 1) % maxSize;return data;}}//显示队列public void showQueue(){if (isEmpty()){System.out.println("队列为空，没有元素可显示！");return;}for (int i = front; i < front + size(); i++) {System.out.printf("arr[%d] = %d\n",i % maxSize,queue[i % maxSize]);}}//求当前队列有效数据个数public int size(){return (rear + maxSize - front) % maxSize;}//显示头数据public void headQueue(){if (isEmpty()){throw new RuntimeException("队列为空，没有头数据！");}System.out.println(queue[front]);}}②测试类123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.Scanner;/*** @Author: Yeman* @Date: 2021-10-11-22:02* @Description:*/public class ArrayQueueTest {public static void main(String[] args) {//创建一个队列ArrQueue arrQueue = new ArrQueue(3); //说明该环形队列的最大有效数据为2//创建一个用户输入Scanner scanner = new Scanner(System.in);//创建一个功能菜单char key = ' ';boolean isShow = true;while (isShow){System.out.println("s:显示队列");System.out.println("a:添加数据");System.out.println("g:取出数据");System.out.println("h:显示头数据");System.out.println("e:退出程序");key = scanner.next().charAt(0);switch (key){case 's' :arrQueue.showQueue();break;case 'a' :System.out.println("请输入一个数：");int value = scanner.nextInt();arrQueue.addQueue(value);break;case 'g' :try {System.out.println(arrQueue.getQueue());} catch (Exception e) {e.printStackTrace();}break;case 'h' :try {arrQueue.headQueue();} catch (Exception e) {e.printStackTrace();}break;case 'e' :isShow = false;break;}}System.out.println("程序退出...");}}