队列介绍

队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

数组模拟队列

思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变。
front 指向队列头部，分析出front是指向队列头的前一个位置
rear 指向队列尾部，分析出rear是指向队列尾部的数据（即队列最后一个数据）
将尾指针往后移：rear+1
当front == rear ，队列为空
若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。当rear == maxSize - 1，说明队列已满。
示例代码
```java package com.concise.demo.data_structure.queue;

import java.util.Scanner;

/**

使用数组模拟一个队列
@author shenguangyang

@date 2022-02-27 9:54 */ public class ArrayQueue { public static void main(String[] args) {

 boolean loop = true;
 System.out.println("a [add], 添加数据");
 System.out.println("g [get], 获取数据");
 System.out.println("sa [showAll], 展示全部数据");
 System.out.println("sh [showHeader], 展示头部数据");
 System.out.println("e [exit], 退出");
 ArrayQueue queue = new ArrayQueue(4);
 Scanner scanner = new Scanner(System.in);
 while (loop) {
     String key = scanner.nextLine();
     switch(key) {
         case "a":
             try {
                 System.out.print("请输入一个数字: ");
                 int data = scanner.nextInt();
                 queue.add(data);
             } catch (Exception e) {
                 System.err.println(e.getMessage());
             }
             break;
         case "g":
             try {
                 System.out.println(queue.get());
             } catch (Exception e) {
                 System.err.println(e.getMessage());
             }
             break;
         case "sa":
             try {
                 queue.showAll();
             } catch (Exception e) {
                 System.err.println(e.getMessage());
             }
             break;
         case "sh":
             try {
                 queue.showHeader();
             } catch (Exception e) {
                 System.err.println(e.getMessage());
             }
             break;
         case "e":
             loop = false;
             break;
         default:
             break;
     }
 }
 System.out.println("程序退出了");

}

private final int[] arr; /**

数组队列头部 / private int front; /*
数组队列尾部 / private int real; /*
表示数组队列的最大容量 */ private final int maxSize;

public ArrayQueue(int maxSize) { this.maxSize = maxSize; this.arr = new int[maxSize]; // 指向队列头部，front是指向队列头部数据的前一个位置 this.front = -1; // 指向队列尾部，rear是指向队列尾部数据 this.real = -1; }

/**
判断队列是否已满
@return */ public boolean isFull() { // rear队列尾部数据==最大容量，说明队列已满 return this.real == this.maxSize - 1; }

/**
判断队列是否为空
@return */ public boolean isEmpty() { // 队列头部指针==队列尾部指针，说明队列为空 return this.real == this.front; }

public void add(int data) { if (this.isFull()) {
```
 throw new RuntimeException("队列已经满了");
```
} // 队列尾部指针向后移 this.real = this.real + 1; this.arr[this.real] = data; }

public int get() { if (this.isEmpty()) {
```
 throw new RuntimeException("队列为空");
```
} // 队列头部指针向后移动 this.front = this.front + 1; return this.arr[this.front]; }

public void showAll() { if (this.isEmpty()) {
```
 throw new RuntimeException("队列为空");
```
} for (int i = 0; i < this.arr.length; i++) {
```
 System.out.printf("\tarr[%d] = %d\n", i, this.arr[i]);
```
} }

public void showHeader() { if (this.isEmpty()) {
```
 throw new RuntimeException("队列为空");
```
} System.out.printf(“\tarr[%d] = %d\n”, this.front + 1, this.arr[this.front + 1]); } } ```

测试结果如下

a [add], 添加数据
g [get], 获取数据    
sa [showAll], 展示全部数据
sh [showHeader], 展示头部数据
e [exit], 退出
a
请输入一个数字: 10
sa
    arr[0] = 10
    arr[1] = 0
    arr[2] = 0
    arr[3] = 0
sh
    arr[0] = 10
a
请输入一个数字: 20
sa
    arr[0] = 10
    arr[1] = 20
    arr[2] = 0
    arr[3] = 0
sh
    arr[0] = 10
a
请输入一个数字: 30
a
请输入一个数字: 40
a
请输入一个数字: 50
队列已经满了
sa
    arr[0] = 10
    arr[1] = 20
    arr[2] = 30
    arr[3] = 40
g
10
g
20
g
30
sh
    arr[3] = 40
g
40
sh
队列为空
e
程序退出了
Process finished with exit code 0

问题分析并优化思路

问题：目前数组使用一次就不能用，没有达到复用的效果
优化思路：将这个数组使用算法，改进成一个环形的队列取模的方式

当数据从队列全部取出之后，再添加数据, 不能添加, 说明数组使用一次就不能再次使用，没有达到复用效果

数组模拟环形队列

实现:让数组达到复用的效果，即：当我们从数组队列中取出了数据，那取出数据后后这个空间可以再次使用

思路分析

当rear指针指向maxsize - 1时，也就是当rear = maxsize - 1 时，需要判断rear的前面是否有空闲空间,也就是说front是否产生了变化并且已经不在初始的那个位置了

思路如下：

front的含义做调整：front由原来的指向队列头的前一个位置调整为现在的front指向了队列头
队列头：就是队列中第一个数据所在的位置
即：queueArr[front]就是获取的队列中的第一个数据

说明：

原来front的初始值为 - 1 现在 front 的初始值为0
原来的front是不包含队列头的，现在的front是包含队列头的
rear的含义做调整：rear从原来指向队列的最后一个数据调整为了现在的rear指向队列的最后一个数据的前一个位置
调整rear的目的：预留一个空间作为约定

说明：

原来的rear的初始值为 - 1，现在的rear的初始值为0
原来的rear包含队列的最后一个数据，现在的rear是不包含队列的最后一个数据。
预留的空间是动态变化的，预留空间始终都在rear指向的最后一个数据的后一个位置
rear和front含义发生调整后，判断队列满的条件是( rear + 1 )% maxsize = front
为什么要取模？答：因为rear可能是一直增长的，从而达到数组空间复用的效果, 如果不进行取模会出现数组越界情况
原先队列满的条件是rear = maxsize - 1 因为原先没有考虑数组空间的复用

判断队列为空的条件是rear = front

经过以上分析

当rear和front含义发生调整后，队列中有效数据的个数是 (rear + maxsize - front) % maxsize
为什么要取模？答：因为是环形队列，rear有可能指到队列最前面。
为什么要加上maxsize?
- 因为是环形队列，rear有可能指到队列最前面, 所以 rear - front 很有可能为负数, 这时候 (rear - front) + maxsize就是有效个数, 如果不为负数, 需要进行 % maxsize, 才能保证结果为有效个数
打个比方,当rear = 0,maxsize = 4 ,front = 0时，该队列中有多少个有效的数据？

分析：（0 + 3 - 0）% 3 = 0，该队列中有效的数据个数为0个，因为rear = front ，则证明是空队列

代码实现

package com.concise.demo.data_structure.queue;
import java.util.Scanner;
/**
 * 使用数组模拟一个环形队列
 * @author shenguangyang
 * @date 2022-02-27 9:54
 */
public class CirCleArrayQueue {
    public static void main(String[] args) {
        boolean loop = true;
        System.out.println("a [add], 添加数据");
        System.out.println("g [get], 获取数据");
        System.out.println("sa [showAll], 展示全部数据");
        System.out.println("sh [showHeader], 展示头部数据");
        System.out.println("e [exit], 退出");
        CirCleArrayQueue queue = new CirCleArrayQueue(4);
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            String key = scanner.nextLine();
            switch(key) {
                case "a":
                    try {
                        System.out.print("请输入一个数字: ");
                        int data = scanner.nextInt();
                        queue.add(data);
                    } catch (Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break;
                case "g":
                    try {
                        System.out.println(queue.get());
                    } catch (Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break;
                case "sa":
                    try {
                        queue.showAll();
                    } catch (Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break;
                case "sh":
                    try {
                        queue.showHeader();
                    } catch (Exception e) {
                        System.err.println(e.getMessage());
                    }
                    break;
                case "e":
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出了");
    }
    private final int[] arr;
    /**
     * front 调整后的含义为： 指向队列头（即：队列中的第一个数据），front的初始值为 0
     */
    private int front;
    /**
     * rear 调整后的含义为：指向队列中的最后一个数据的前一个位置 ，rear 的初始值为0
     */
    private int real;
    /**
     * maxsize 表示队列的最大容量，队列中的数据是存放在数组中的
     */
    private final int maxSize;
    public CirCleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.front = 0;
        this.real = 0;
    }
    /**
     * 判断队列是否已满
     */
    public boolean isFull() {
        return (this.real + 1) % maxSize == this.front;
    }
    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return this.real == this.front;
    }
    public void add(int data) {
        if (this.isFull()) {
            throw new RuntimeException("队列已经满了");
        }
        this.arr[this.real] = data;
        this.real = (this.real + 1) % this.maxSize;
    }
    public int get() {
        if (this.isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        // 第一步 先把queueArr[front]对应的保存在一个临时变量中
        // 为什么要将queueArr[front]对应的保存在一个临时变量中? 因为 若直接返回的话,就没有往后移的机会了
        int value = this.arr[this.front];
        this.front = (this.front + 1) % this.maxSize;
        return value;
    }
    public void showAll() {
        if (this.isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("\tarr[%d] = %d\n", i % this.maxSize, this.arr[i % this.maxSize]);
        }
    }
    public void showHeader() {
        if (this.isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        System.out.printf("\tarr[%d] = %d\n", this.front, this.arr[this.front]);
    }
    public int size() {
        return (this.real + this.maxSize - this.front) % this.maxSize;
    }
}

队列

队列介绍

数组模拟队列

思路

示例代码

问题分析并优化思路

数组模拟环形队列

思路分析

代码实现