队列（queue）
队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue
顺序队列
数组实现的队列叫顺序队列
用front来标记与队头元素位置的关系
用rear来标记与队尾元素位置的关系
如下：当队列为空时，设置front=rear=-1
（-1为初始值，不代表索引）, 当添加元素时：
rear=数组长度-1时该队列已满。此时rear=maxSize-1；front还是在队头的前面。
删除元素：
注意: 所谓的删除，其实就是通过操作front和rear与队头队尾元素索引的关系，使我们访问不到元素，实际上元素还在队列里面
public class ArrayQueueDemo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayQueue arrayQueue = new ArrayQueue(3);
boolean flag=true;
while (flag) {
System.out.println("请输入：(s:显示队列,a:添加队列,g:取出数据,h:查看队头数据,e:退出)");
switch (sc.next().charAt(0)) {
case 's':
try {
arrayQueue.listQueue();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'a':
System.out.println("请输入：");
try {
arrayQueue.addQueue(sc.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'g':
try {
int queue = arrayQueue.getQueue();
System.out.println(queue);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int i = arrayQueue.headQueue();
System.out.println(i);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
flag=false;
break;
default:
System.out.println("输入有误！！");
break;
}
}
}
}
class ArrayQueue{ // 数组实现队列
private int maxSize; // 数组容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 模拟队列的数组
//队列构造器
public ArrayQueue(int arrMaxSize){
maxSize=arrMaxSize;
arr=new int[arrMaxSize];
front=-1; // 记录队列头索引的前一个位置
rear=-1; // 记录队列尾索引
}
//判断队列是否为空
public boolean isEmpty() {
return rear==front;
}
//判断队列是否满
public boolean isFull() {
return rear==maxSize-1;
}
// 添加数据到队列
public void addQueue(int n){
//判断是否满
if (isFull()){
throw new RuntimeException("队列满，不能添加数据");
}
rear++; //后移1位
arr[rear]=n;
}
//取出队列数据,出队列
public int getQueue() {
//判断队列是否为空
if (isEmpty()){
throw new RuntimeException("队列空，不能获取数据");
}
front++; // 后移
return arr[front];
}
//显示队列所有元素
public void listQueue() {
//判空
if (isEmpty()) {
throw new RuntimeException("队列空，无数据");
}
for (int i = 0; i < arr.length; i++) {
if (i==0){
System.out.print("[ "+arr[i]);
}else if (i==maxSize-1){
System.out.print(","+arr[i]+" ]");
}else {
System.out.print(","+arr[i]);
}
}
}
//显示头数据
public int headQueue() {
if (isEmpty()){
throw new RuntimeException("队列为空，无数据");
}
return arr[front+1];
}
}
缺点：使队列空间只能使用一次，不能重复使用。
这种情况称为"假溢出"（入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用，队列队列满时rear=maxSize-1,还要添加元素，则rear+1就会>数组的索引）
环形队列(数组)
在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。
队列中有效数据个数为：(rear+maxSize-front)%maxSize，如上图：(3+4-0)%4=3
实现环形队列：
取出元素front=(front+1)%maxSize，当front到队列末尾时有回到起点：front=0，形成循环
添加元素：rear=(rear+1)%maxSize，当队列满时，rear=0，回到起点形成循环
package com.pqy.linear.queue;
import java.util.Scanner;
/**
* @author panqiyi
* @date 2021/9/25 - 15:20
*/
class CircleArray {
private int maxSize; // 数组容量
private int front; // 队列头,默认0
private int rear; // 队列尾
private int[] arr; // 模拟队列的数组
//队列构造器
public CircleArray(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[arrMaxSize];
}
//判断队列是否为空
public boolean isEmpty() {
return rear == front;
}
//判断队列是否满
public boolean isFull() {
return (rear+1)%maxSize==front;
}
// 添加数据到队列
public void addQueue(int n) {
//判断是否满
if (isFull()) {
throw new RuntimeException("队列满，不能添加数据");
}
arr[rear] = n;
rear=(rear+1)%maxSize; // 后移取模
}
//取出队列数据,出队列
public int getQueue() {
//判断队列是否为空
if (isEmpty()) {
throw new RuntimeException("队列空，不能获取数据");
}
int value=arr[front];
front=(front+1)%maxSize; // 后移取模
return value;
}
//显示队列所有元素
public void listQueue() {
//判空
if (isEmpty()) {
throw new RuntimeException("队列空，无数据");
}
for (int i = front; i < front+size(); i++) { // 队头+有效元素个数
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
//求有效数据个数
public int size(){
return (rear+maxSize-front)%maxSize;
}
//显示头数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列为空，无数据");
}
return arr[front];
}
}
public class CircleArrayQueueDemo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
CircleArray circleArray = new CircleArray(3);
boolean flag=true;
while (flag) {
System.out.println("请输入：(s:显示队列,a:添加队列,g:取出数据,h:查看队头数据,e:退出)");
switch (sc.next().charAt(0)) {
case 's':
try {
circleArray.listQueue();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'a':
System.out.println("请输入：");
try {
circleArray.addQueue(sc.nextInt());
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'g':
try {
int queue = circleArray.getQueue();
System.out.println(queue);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int i = circleArray.headQueue();
System.out.println(i);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
flag=false;
break;
default:
System.out.println("输入有误！！");
break;
}
}
}
}
运行：
2、设置数组大小为3
2、输入 11，22
3、取出一个元素
4、添加一个元素
// 添加数据到队列
public void addQueue(int n) {
//判断是否满
if (isFull()) {
throw new RuntimeException("队列满，不能添加数据");
}
arr[rear] = n; //添加元素
rear=(rear+1)%maxSize; // 后移取模
}
5、查看队列
//显示队列所有元素
public void listQueue() {
//判空
if (isEmpty()) {
throw new RuntimeException("队列空，无数据");
}
for (int i = front; i < front+size(); i++) { // 队头开始到 队头+有效元素个数
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
//求有效数据个数
public int size(){
return (rear+maxSize-front)%maxSize;
}
为什么要 i%maxSize ? 因为这样才能得到准确的元素索引（再删除添加一个元素就知道了，添加44）
再查看
因为是循环队列，所有遍历有效的数据，front到front+size()可能是在不同方向的，front与rear都是取模的，所以索引也取模才能得到。