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

队列简介

队列是一个有序列表，可以用数组或是链表来实现。

遵循先入先出的原则。即先存入队列的数据，先取出，后存入的后取出。

示意图：(使用数组模拟队列示意图)

有两个分别指向头部和尾部的“指针”。

数组模拟队列（无法复用）

1、实现思路

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：

当我们将数据存入队列时称为addQueue，addQueue的处理需要有两个步骤：
①将尾指针往后移。
②若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear 所指的数组元素中，否则无法存入数据。

rear+1当front== rear[空]
rear==maxSize-1[队列满]

2、代码实现

①数组实现队列类

class 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]);
   }

}

②测试类

import 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、代码实现

①数组实现环形队列类

class 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]);
   }

}

②测试类

import 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("程序退出...");
   }
}

来源：https://blog.csdn.net/m0_46653805/article/details/120712729