队列是一个有序列表，可以用数组或是链表来实现。
遵循先进先出的原则。
image.png

1、数组模拟队列思路

队列本身是有序队列，若用数组结构来存储队列的数据，则队列数据的声明如下图，其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标，front 会随着数据输出而改变，如图所示：
image.png
当我们将数据存入队列时称为“addQueue”, addQueue 的处理需要有两个步骤： 思路分析
1）将尾针往后移： rear+1,当front == rear【空】
2）若尾指针 rear 小于最大下标 maxSize-1 ,则将数据存入rear若之的数组元素中，否则无法存入数据。rear ==maxSize - 1【队列满】
代码如下：

  1. package com;
  3. import java.util.Scanner;
  5. public class ArrayQueueDemo {
  6.     public static void main(String[] args) {
  7.         ArrayQueue Queue = new ArrayQueue(3);
  8.         char key = ' ';//接受用户输入
  9.         Scanner scan = new Scanner(System.in);
  10.         boolean loop = true;
  11.         // 输出一个菜单
  12.         while(loop){
  13.             System.out.println("s(show): 显示队列");
  14.             System.out.println("e(exit): 退出程序");
  15.             System.out.println("a(add): 添加数据到队列");
  16.             System.out.println("g(get): 从队列取出数据");
  17.             System.out.println("h(head): 查看队列头的数据");
  18.             key =scan.next().charAt(0);//接受一个字符
  19.             switch (key){
  20.                 case 's':
  21.                     Queue.showQueue();
  22.                     break;
  23.                 case 'a':
  24.                     System.out.println("请输入一个数字");
  25.                     int value = scan.nextInt();
  26.                     Queue.addQueue(value);
  27.                     break;
  28.                 case 'g':
  29.                     try {
  30.                         int res = Queue.getQueue();
  31.                         System.out.printf("取出的数据是：%d\n",res);
  32.                     }catch (Exception e){
  33.                         System.out.println(e.getMessage());
  34.                     }
  35.                     break;
  36.                 case 'h':
  37.                     try {
  38.                         int res = Queue.headQueue();
  39.                         System.out.printf("队列头的数据是：%d\n",res);
  40.                     }catch (Exception e){
  41.                         System.out.println(e.getMessage());
  42.                     }
  43.                     break;
  44.                 case 'e':
  45.                     scan.close();
  46.                     loop = false;
  47.                 default:
  48.                     break;
  49.             }
  50.         }
  51.         System.out.println("程序退出");
  52.     }
  53. }
  55. class ArrayQueue{
  56.     private int maxSize;//表示数组的最大容量
  57.     private int front;// 队列头
  58.     private int rear;// 队列尾
  59.     private int[] arr;
  61.     // 创建队列的构造器
  62.     public ArrayQueue(int arrMaxSize){
  63.         maxSize = arrMaxSize;
  64.         arr = new int[arrMaxSize];
  65.         front = -1; //指向队列头部，分析出front是指向队列头的前一个位置。
  66.         rear = -1;// 指向队列尾，指向队列尾的数据（即就是队列最后一个数据）
  67.     }
  69.     // 判断队列数据是否满
  70.     public boolean isFull(){
  71.         return rear == maxSize - 1;
  72.     }
  74.     public void addQueue(int n){
  75.         // 判断队列是否满
  76.         if(isFull()){
  77.             System.out.println("队列满，不能加入数据");
  78.             return;
  79.         }
  80.         rear++;// 让rear后移
  81.         arr[rear] = n;
  82.     }
  83.     // 判断是否为空
  84.     public boolean isEmpty(){
  85.         return rear == front;
  86.     }
  87.     // 获取队列数据
  88.     public int getQueue(){
  89.         if (isEmpty()){
  90.             //通过抛出异常
  91.             throw new RuntimeException("队列为空");}
  92.         front++;// 将front后移
  93.         return arr[front];
  94.     }
  95.     // 显示队列所有数据
  96.     public void showQueue(){
  97.         // 遍历
  98.         if(isEmpty()){
  99.             System.out.println("队列空的，没有数据~~~");
  100.             return;
  101.         }
  102.         for (int i=0; i<arr.length;i++){
  103.             System.out.printf("arr[%d]=%d\n", i, arr[i]);
  104.         }
  106.     }
  107.     // 显示队列的头数据，注意不是取出数据
  108.     public int headQueue(){
  109.         //判断
  110.         if(isEmpty()){
  111.             throw new RuntimeException("队列为空");
  112.         }
  113.         return  arr[front + 1];
  114.     }
  115. }

注意：以上代码所实现的是一个一次性队列，不能添加，因为头front和尾rear是往后移动的，所以要进行优化为环形队列，通过取模来实现。

2. 数组模拟环形队列

image.png

image.png

利用模运算：rear = rear + 1 ;if (rear==maxsize) rear = 0
可转化为：rear = (rear + 1)%maxsize
出队则：
front = (front +1)%maxsize
遍历：(rear+maxsize-front)%maxsize

  1. public class ArrayQueueDemo2 {
  2.     public static void main(String[] args) {
  3.         circleArrayQueue Queue = new circleArrayQueue(4);
  4.         char key = ' ';//接受用户输入
  5.         Scanner scan = new Scanner(System.in);
  6.         boolean loop = true;
  7.         // 输出一个菜单
  8.         while(loop){
  9.             System.out.println("s(show): 显示队列");
  10.             System.out.println("e(exit): 退出程序");
  11.             System.out.println("a(add): 添加数据到队列");
  12.             System.out.println("g(get): 从队列取出数据");
  13.             System.out.println("h(head): 查看队列头的数据");
  14.             key =scan.next().charAt(0);//接受一个字符
  15.             switch (key){
  16.                 case 's':
  17.                     Queue.showQueue();
  18.                     break;
  19.                 case 'a':
  20.                     System.out.println("请输入一个数字");
  21.                     int value = scan.nextInt();
  22.                     Queue.addQueue(value);
  23.                     break;
  24.                 case 'g':
  25.                     try {
  26.                         int res = Queue.getQueue();
  27.                         System.out.printf("取出的数据是：%d\n",res);
  28.                     }catch (Exception e){
  29.                         System.out.println(e.getMessage());
  30.                     }
  31.                     break;
  32.                 case 'h':
  33.                     try {
  34.                         int res = Queue.headQueue();
  35.                         System.out.printf("队列头的数据是：%d\n",res);
  36.                     }catch (Exception e){
  37.                         System.out.println(e.getMessage());
  38.                     }
  39.                     break;
  40.                 case 'e':
  41.                     scan.close();
  42.                     loop = false;
  43.                     break;
  44.                 default:
  45.                     break;
  46.             }
  47.         }
  48.         System.out.println("程序退出");
  49.     }
  50. }
  52.     class circleArrayQueue{
  53.         private int maxSize;//表示数组的最大容量
  54.         private int front;// 队列头
  55.         private int rear;// 队列尾
  56.         private int[] arr;
  58.         // 创建队列的构造器
  59.     public circleArrayQueue(int arrMaxSize){
  60.         maxSize = arrMaxSize;
  61.         arr = new int[arrMaxSize];
  62.         //front = 0; //指向队列第一个元素，分析出front是指向队列头的前一个位置。
  63.         //rear = 0;// 指向队列的最后一个位置，因为希望空出一个位置，指向队列尾的数据（即就是队列最后一个数据）
  64.     }
  66.     // 判断队列数据是否满
  67.     public boolean isFull(){
  68.         return (rear+1)%maxSize == front;
  69.     }
  71.     public void addQueue(int n){
  72.         // 判断队列是否满
  73.         if(isFull()){
  74.             System.out.println("队列满，不能加入数据");
  75.             return;
  76.         }
  77.         arr[rear] = n;
  78.         rear = (rear+1)% maxSize;//考虑取模
  79.     }
  80.     // 判断是否为空
  81.     public boolean isEmpty(){
  82.         return rear == front;
  83.     }
  84.     // 获取队列数据
  85.     public int getQueue(){
  86.         if (isEmpty()){
  87.             //通过抛出异常
  88.             throw new RuntimeException("队列为空");
  89.         }
  91.         int value = arr[front];
  92.         front = (front+1)%maxSize;// 将front后移，考虑取模
  93.         return value;
  94.     }
  95.     // 显示队列所有数据
  96.     public void showQueue(){
  97.         // 遍历
  98.         if(isEmpty()){
  99.             System.out.println("队列空的，没有数据~~~");
  100.             return;
  101.         }
  102.         for (int i=front; i<front + size();i++){
  103.             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
  104.         }
  106.     }
  107.     //求当前队列有效数据的个数
  108.     public int size(){
  109.         return (rear + maxSize - front) % maxSize;
  110.     }
  111.     // 显示队列的头数据，注意不是取出数据
  112.     public int headQueue(){
  113.         //判断
  114.         if(isEmpty()){
  115.             throw new RuntimeException("队列为空");
  116.         }
  117.         return  arr[front];
  119.     }
  120. }