极简Java数据结构-环形队列突破上限

👨🏻‍🎓博主介绍：大家好，我是芝士味的椒盐，一名在校大学生，热爱分享知识，很高兴在这里认识大家🌟
🌈擅长领域：Java、大数据、运维、电子
🙏🏻如果本文章各位小伙伴们有帮助的话，🍭关注+👍🏻点赞+🗣评论+📦收藏，相应的有空了我也会回访，互助！！！
🤝另本人水平有限，旨在创作简单易懂的文章，在文章描述时如有错，恳请各位大佬指正，在此感谢！！！

@[TOC]

什么是队列

• 队列是一个有序的列表，可以用数组或是链表实现
• 队列遵循先入先出的原则。即将：先存入队列的数据要先取出，后存入的要后取出
  
  • 若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
  • 队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变
    
  • 将尾指针往后移：rear+1 , 当front == rear 【空】
  • 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]
  • rear 是队列最后[含]
  • front 是队列最前元素[不含]

普通队列代码实现

• 数组模拟队列案例：

  package icu.lookyousmileface.arrayqueue;
  
  import java.util.Scanner;
  
  /**
   * @author 芝士味的椒盐
   * @title: ArrayQueueDemo
   * @projectName DataStructure_Algorithm
   * @date 2020/12/14 15:56
   */
  public class ArrayQueueDemo {
      public static void main(String[] args) {
  //        ArrayQueue arrayQueue = new ArrayQueue(4);
  ////        System.out.println(arrayQueue.getQueue());
  //        System.out.println(arrayQueue.isEmpty());
  //        arrayQueue.addQueue(5);
  //        arrayQueue.addQueue(4);
  //        arrayQueue.addQueue(3);
  //        System.out.println(arrayQueue.isFull());
  //        arrayQueue.addQueue(2);
  
  //        arrayQueue.showQueue();
  
  //        System.out.println(arrayQueue.isEmpty());
  //        System.out.println(arrayQueue.isFull());
  //        System.out.println(arrayQueue.getQueue());
  //        System.out.println(arrayQueue.getFirst());
  //        System.out.println(arrayQueue.getLast());
  
          ArrayQueue arrayQueue = new ArrayQueue(4);
          char key = ' ';
          Scanner scanner = new Scanner(System.in);
          boolean loop = true, status = true;
          while (loop && status) {
              System.out.println("注意：使用add的是时候，添加的只能是数字，比如：先输入add回车，在输入要存的数字1024回车");
              System.out.println("show(s):查看所有的队列元素");
              System.out.println("add(a): 添加元素");
              System.out.println("get(g)：取出数据");
              System.out.println("head(h)：获取头部元素");
              System.out.println("exit(e)：退出程序");
              key = scanner.next().charAt(0);
              switch (key) {
                  case 's':
                      arrayQueue.showQueue();
                      break;
                  case 'a':
                      int value = new Scanner(System.in).nextInt();
                      arrayQueue.addQueue(value);
                      break;
                  case 'g':
                      try {
                          int queue = arrayQueue.getQueue();
                          System.out.println("取出数据" + queue);
                      } catch (Exception e) {
                          e.printStackTrace();
                      }
                      break;
                  case 'h':
                      try {
                          int first = arrayQueue.getFirst();
                          System.out.println("你取出了头部元素" + first);
                      } catch (Exception e) {
                          e.printStackTrace();
                      }
                      break;
                  case 'e':
                      status = false;
                      break;
                  default:
                      break;
              }
          }
  
      }
  }
  
  /**
   * @author 芝士味的椒盐
   * @title: ArrayQueue
   * @date 2020/12/14  16:00
   * 模拟队列
   */
  class ArrayQueue {
      private int maxSize;
      private int front;
      private int rear;
      private int[] arr;
  
      public ArrayQueue(int maxSize) {
          this.maxSize = maxSize;
          this.front = -1;
          this.rear = -1;
          this.arr = new int[maxSize];
      }
  
      public boolean isEmpty() {
          return this.rear == this.front;
      }
  
      public boolean isFull() {
          return this.rear == this.maxSize - 1;
      }
  
      public void addQueue(int num) {
          if (isFull()) {
              System.out.println("Queue is Full！");
              return;
          }
          this.arr[++this.rear] = num;
      }
  
      public int getQueue() {
          if (isEmpty()) {
              //抛出异常相当return的效果，后面代码无法执行
              throw new RuntimeException("Queue is Empty not get value!");
          }
          return this.arr[++this.front];
      }
  
      public void showQueue() {
          if (isEmpty()) {
              System.out.println("Queue is Empty, not showQueue!");
              return;
          }
          for (int i = 0; i < this.arr.length; i++) {
              System.out.printf("arr[%d] = %d\n", i, arr[i]);
          }
      }
  
      public int getFirst() {
          if (isEmpty()) {
              throw new RuntimeException("Queue is Empty,not getFirst element!");
          }
          return this.arr[++this.front];
      }
  
      public int getLast() {
          if (isEmpty()) {
              throw new RuntimeException("Queue is Empty,not getLast element!");
          }
          return this.arr[this.arr.length - 1];
      }
  }
  
  

  • 代码缺点：底层实现的数组无法重用，尾索引处于满的状态

什么是环形队列

• 环形数组模拟队列：
  可以弥补上述队列尾索引处于满存在队列上限问题，这样队列就可以将队列无限次使用。
  

环形队列代码实现

		package icu.lookyousmileface.circlearrayqueue;
		
		import java.util.Scanner;
		
		/**
		 * @author 芝士味的椒盐
		 * @title: CircleArrayQueueDemo
		 * @projectName DataStructure_Algorithm
		 * @date 2020/12/14 22:23
		 */
		public class CircleArrayQueueDemo {
		    public static void main(String[] args) {
		        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(5);
		        Scanner scanner = new Scanner(System.in);
		        char key = ' ';
		        boolean loop = true;
		        boolean status = true;
		        while (loop&&status) {
		            System.out.println("注意：使用add的是时候，添加的只能是数字，比如：先输入add回车，在输入要存的数字1024回车");
		            System.out.println("show(s):查看所有的队列元素");
		            System.out.println("add(a): 添加元素");
		            System.out.println("get(g)：取出数据");
		            System.out.println("head(h)：获取头部元素");
		            System.out.println("exit(e)：退出程序");
		            key = scanner.next().charAt(0);
		            switch (key) {
		                case 's':
		                    circleArrayQueue.showQueue();
		                    break;
		                case 'a':
		                    try{
		                        int value = scanner.nextInt();
		                        circleArrayQueue.addQueue(value);
		                    }catch (Exception e){
		                        System.out.println("队列已满，无法加入新元素");
		                    }
		                    break;
		                case 'g':
		                    try {
		                        int queue = circleArrayQueue.getQueue();
		                        System.out.println("取出元素 :" + queue);
		                    } catch (Exception e) {
		                        System.out.println("无法取，队列为空");
		                    }
		                    break;
		                case 'h':
		                    try {
		                        int head = circleArrayQueue.getHead();
		                        System.out.println("头部元素 :" + head);
		                    }catch (Exception e){
		                        System.out.println("无法获取，头部为Null");
		                    }
		                    break;
		                case 'e':
		                    status = false;
		                    break;
		                default:
		                    break;
		            }
		        }
		    }
		}
		
		/**
		 * @author 芝士味的椒盐
		 * @title: CircleArrayQueue
		 * @date 2020/12/14  22:26
		 * 环形队列
		 */
		class CircleArrayQueue {
		    private int maxSize;
		    private int front;
		    private int rear;
		    private int[] arr;
		
		    public CircleArrayQueue(int maxSize) {
		        this.maxSize = maxSize;
		        this.arr = new int[this.maxSize];
		    }
		
		    public boolean isFull() {
		        return (this.rear + 1) % maxSize == front;
		    }
		
		    public boolean isEmpty() {
		        return this.rear == this.front;
		    }
		
		    public void addQueue(int num) {
		        if (isFull()) {
		            throw new RuntimeException("Queue is Full!");
		        }
		        this.arr[this.rear] = num;
		        //将rear后移，考虑取模
		        rear = (rear + 1) % maxSize;
		    }
		
		    public int getQueue() {
		        if (isEmpty()) {
		            throw new RuntimeException("Queue is Empty!");
		        }
		        // 这里需要分析出 front是指向队列的第一个元素
		        // 1. 先把 front 对应的值保留到一个临时变量
		        // 2. 将 front 后移, 考虑取模
		        // 3. 将临时保存的变量返回
		        int value = this.arr[this.front];
		        front = (front + 1) % maxSize;
		        return value;
		    }
		
		    /**
		     * @author 芝士味的椒盐
		     * @title: size
		     * @date 2020/12/14  22:48
		     * 环形链表有效个数
		     */
		    public int size() {
		        return (this.rear + this.maxSize - this.front) % maxSize;
		    }
		
		    public void showQueue() {
		        if (isEmpty()) {
		            throw new RuntimeException("Queue is Empty!");
		        }
		        for (int i = this.front; i < this.front + size(); i++) {
		            System.out.printf("arr[%d] = %d\n", i % maxSize, this.arr[i % maxSize]);
		        }
		    }
		
		    public int getHead() {
		        if (isEmpty()) {
		            throw new RuntimeException("Queue is Empty!");
		        }
		        return arr[this.front];
		    }
		
		}
		

思路如下:
1.  front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 
front 的初始值 = 0
2.  rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
rear 的初始值 = 0
3. 当队列满时，条件是  (rear  + 1) % maxSize == front 【满】
4. 对队列为空的条件， rear == front 空
5. 队列中有效的数据的个数   (rear + maxSize - front) % maxSize   // rear = 1 front = 0