1）队列是一个有序列表，可以用数组或者链表实现
2）遵循先入先出的原则

使用数组实现队列

图片1.png
示意图
front：为对首标志，表示队列数组队首的下标-1
rear：为对尾标志，表示队列数组队尾的下标

  1. public class ArrayQueueDemo {
  2.     public static void main(String[] args) {
  3.         //创建队列
  4.         ArrayQueue arrayQueue = new ArrayQueue(3);
  5.         Scanner scanner = new Scanner(System.in);
  6.         boolean loop = true;
  7.         while (loop) {
  8.             System.out.println("请输入：");
  9.             System.out.println("1:展示数据");
  10.             System.out.println("2:查看队首");
  11.             System.out.println("3:添加数据");
  12.             System.out.println("4:取出数据");
  13.             System.out.println("5:退出");
  14.             int key = scanner.nextInt();
  15.             switch (key) {
  16.                 case 1:
  17.                     arrayQueue.showQueue();
  18.                     break;
  19.                 case 2:
  20.                     arrayQueue.peek();
  21.                     break;
  22.                 case 3:
  23.                     System.out.println("输入要添加的数据：");
  24.                     int n = scanner.nextInt();
  25.                     arrayQueue.addQueue(n);
  26.                     break;
  27.                 case 4:
  28.                     try{
  29.                         int data = arrayQueue.getQueue();
  30.                         System.out.println("取出数据："+data);
  31.                     }catch (Exception e){
  32.                         String message = e.getMessage();
  33.                         System.out.println(message);
  34.                     }
  35.                     break;
  36.                 case 5:
  37.                     loop = false;
  38.                     break;
  39.                 default:
  40.                     System.out.println("输入有误");
  41.                     break;
  42.             }
  43.         }
  44.     }
  46. }
  48. /**
  49.  * 数组队列自定义类
  50.  */
  51. class ArrayQueue{
  52.     private int maxSize; //表示数组最大容量
  53.     private int front; //指向队首
  54.     private int rear; //指向队尾
  55.     private int[] arr; //队列模拟数组
  57.     public ArrayQueue(int maxSize){
  58.         this.maxSize = maxSize;
  59.         arr = new int[maxSize];
  60.         front = -1; //指向队列前一个位置
  61.         rear = -1; //指向队尾
  62.     }
  64.     //判断队列是否满
  65.     public boolean isFull(){
  66.         //队尾下标等于最大容量-1
  67.         return rear == maxSize - 1;
  68.     }
  70.     //判断是否为空
  71.     public boolean isEmpty(){
  72.         return front == rear;
  73.     }
  75.     //添加数据
  76.     public boolean addQueue(int n){
  77.         //判断队列是否满
  78.         if (isFull()){
  79.             System.out.println("队列已满");
  80.             return false;
  81.         }
  82.         rear++;
  83.         arr[rear] = n;
  84.         return true;
  85.     }
  87.     //取出数据
  88.     public int getQueue(){
  89.         //判断是否空
  90.         if(isEmpty()){
  91.             throw new RuntimeException("队列为空");
  92.         }
  93.         front++;
  94.         return arr[front];
  95.     }
  97.     //显示队列的所有数据
  98.     public void showQueue() {
  99.         if (isEmpty()){
  100.             System.out.println("队列空");
  101.             return;
  102.         }
  103.         for(int i=0;i<arr.length;i++){
  104.             System.out.println("arr["+i+"]="+arr[i]);
  105.         }
  106.     }
  108.     //显示队列头数据
  109.     public void peek(){
  110.         //判断是否空
  111.         if (isEmpty()) {
  112.             System.out.println("队列空");
  113.             return;
  114.         }
  115.         System.out.println(arr[front+1]);
  116.     }
  117. }

以上实现存在问题：无法反复使用，因为队列中的下标会一直往前移动，导致队尾标志rear达到maxSize后无法再添加数据，而前面的空间由于front队首标志变大之后也无法继续使用

问题分析：
1）目前数组使用一次后就不能再用，没有达到复用的效果
2）将这个数组使用算法，改进成环形队列，使用取模：%

改写环形队列

思路分析：
1）front变量含义调整为：front指向队列的第一个元素
2）rear变量含义调整为：指向最后一个元素的后一个空的位置
3）队列满条件：(rear+1)%maxSize == front
4）队列空条件：rear == front
5）队列有效个数：(rear+maxSize-front)%maxSize //rear=1 front=0
图片2.png
图片3.png

  1. package com.cwl;
  3. /**
  4.  * @Author Administrator
  5.  * @Date 2021/2/19 0019 9:09
  6.  * @Version 1.0
  7.  */
  8. public class CircleArrayQueueDemo {
  9.     public static void main(String[] args) {
  10.         CircleArrayQueue circleArrayQueue = new CircleArrayQueue(6);
  11.         circleArrayQueue.offer(0);
  12.         circleArrayQueue.offer(1);
  13.         circleArrayQueue.offer(2);
  14.         circleArrayQueue.offer(3);
  15.         circleArrayQueue.offer(4);
  16.         circleArrayQueue.poll();//front=1
  17.         circleArrayQueue.offer(5);//rear=0
  18.         circleArrayQueue.poll();//front=2
  19.         circleArrayQueue.offer(6);//rear=1
  20.         circleArrayQueue.poll();//front=3
  21.         circleArrayQueue.offer(7);//rear=2
  22.         circleArrayQueue.poll();//front=4
  23.         circleArrayQueue.offer(8);//rear=3
  24.         int i = circleArrayQueue.hasElement();
  25.         System.out.println("有效元素："+i);
  26.         circleArrayQueue.look();
  27.     }
  28. }
  29. class CircleArrayQueue{
  30.     private int maxSize; //最大容量，预留一个位置为空，避免前后端指针重合不易判断满和空
  31.     private int rear; //队列后端指针，指向后端 + 1的位置
  32.     private int front;//队列前端，指向头部
  33.     private int[] arr;//队列，存放数据
  34.     //构造器初始化数组容量
  35.     public CircleArrayQueue(int maxSize){
  36.         this.maxSize = maxSize;
  37.         arr = new int[maxSize];
  38.     }
  39.     //判断满
  40.     public boolean isFull(){
  41.         return (rear + 1) % maxSize == front;
  42.     }
  43.     //判断空
  44.     public boolean isEmpty(){
  45.         return front == rear;
  46.     }
  47.     //返回有效数据个数，最大不超过maxSize-1
  48.     public int hasElement(){
  49.         return (rear + maxSize - front) % maxSize;
  50.     }
  51.     //入队，先判断是否满，若rear达到最大值maxSize将其取模为0
  52.     public void offer(int val){
  53.         if (isFull()){
  54.             System.out.println("满");
  55.             return;
  56.         }
  57.         arr[rear] = val;
  58.         rear ++;
  59.         if (rear == maxSize){
  60.             rear = 0;
  61.         }
  62.     }
  63.     //出队，先判断是否空，若front达到最大值maxSize将其取模为0
  64.     public int poll(){
  65.         if(isEmpty()){
  66.             throw new RuntimeException("空");
  67.         }
  68.         int temp = arr[front];
  69.         front ++;
  70.         if (front == maxSize){
  71.             front = 0;
  72.         }
  73.         return temp;
  74.     }
  75.     //查看队列头，先判断是否空，返回队列头的值，不会出队
  76.     public int peek(){
  77.         if (isEmpty()){
  78.             throw new RuntimeException("空");
  79.         }
  80.         return arr[front];
  81.     }
  82.     //查看队列所有（有效值），当队列满时，实际上只有maxSize-1个有效值，从front开始遍历，大于等于maxSize时取模
  83.     public void look(){
  84.         if (isEmpty()){
  85.             System.out.println("空");
  86.         }
  87.         for (int i = front;i < front + hasElement();i++){
  88.             System.out.println("arr[" + i % maxSize+"]=" + arr[i % maxSize]);
  89.         }
  90.     }
  91. }