[数据结构与算法]【每日学算法——Day02】队列

1. 数组模拟队列

1. 队列本身是有序列表，具有先入先出的特性，可以使用数组或链表来实现。

2. 基础构成：

   1. maxSize：数组的最大容量，按照约定空出一个容量，最多能存如maxSize - 1个数据。
   2. front：队列头索引，初始为-1，指向队列头前一个数据。
   3. rear：队列尾，初始为-1，指向队列尾最后一个数据。

3. 特殊场景：

   1. 队列已满： rear = maxSize - 1
   2. 队列已空： rear = front

4. 基础操作：

   1. 加入数据：(rear < maxSize - 1) rear++； arr[rear] = n
   2. 取出数据：(rear > front) front++； return arr[front]

5. 模拟实现

   import com.sun.java.accessibility.util.EventID;
   
   /**
    * <Description> Queue<br>
    *
    * @author MitsuiYe<br>
    * @version 1.0<br>
    * @taskId <br>
    * @CreateDate 2021/12/4 23:00
    */
   public class Queue {
       /**
        * 队列的最大容量
        */
       private int maxSize;
   
       /**
        * 队列头
        */
       private int front;
   
       /**
        * 队列尾
        */
       private int rear;
   
       /**
        * 数据存储，模拟队列
        */
       private int[] arr;
   
       /**
        * 构造函数
        * @param maxSize 最大容量
        */
       public Queue(int maxSize) {
           this.maxSize = maxSize;
           arr = new int[maxSize];
   
           // 初始化rear, front
           rear = -1;
           front = -1;
       }
   
       /**
        * 队列内添加数据
        * @param num 数字
        */
       public void add(int num) {
           if (isFull()) {
               throw new RuntimeException("Queue is full");
           }
           arr[++rear] = num;
       }
   
       /**
        * 从队列中取出数据
        * @return 取出的数据
        */
       public int push() {
           if (isEmpty()) {
               throw new RuntimeException("Queue is empty");
           }
           return arr[++front];
       }
   
       /**
        * 队列是否为空
        */
       public boolean isEmpty() {
           return front == rear;
       }
   
       /**
        * 队列是否满
        */
       public boolean isFull() {
           return rear == maxSize - 1;
       }
   }
   

6. 问题点: 数组不可复用, 只能使用一次(解决方案: 通过%取模构建环形队列, 复用数组)

2. 环形队列

1. 基本构造

   1. front：指向队列第一个元素，但是初始值为0
   2. rear：指向队列最后一个元素的后一个位置，初始值为0
   3. 队列已满：（rear + 1）% maxSize == front
   4. 队列为空：rear == front
   5. 队列的有效个数：（rear + maxSize - front）% maxSize
   6. 为了区分空和满的情况，环形队列默认空出一个位置

2. 基础操作

   1. 加入数据：arr[rear] = n, rear = (rear + 1) % maxSize

   2. 取出数据：

      1. 临时变量保存arr[front]
      2. front = （front + 1）% maxSize
      3. 返回临时变量

   3. 显示所有

      （int i = front，i < 有效个数 + front， i++）
      arr[i % maxSize]
      

3. 代码实现

   /**
    * <Description> CircleQueue<br>
    *
    * @author MitsuiYe<br>
    * @version 1.0<br>
    * @taskId <br>
    * @CreateDate 2021/12/7 23:38
    * @see PACKAGE_NAME <br>
    */
   public class CircleQueue {
   
       /**
        * 数组最大容量，队列可使用的为maxSize - 1
        */
       private int maxSize;
   
       /**
        * 队列头， 指向队列第一个元素，初始值取0
        */
       private int front;
   
       /**
        * 队列尾， 指向队列最后一个元素后一位，初始值取0
        */
       private int rear;
   
       /**
        * 数组
        */
       private int[] arr;
   
       public CircleQueue(int maxSize) {
           this.maxSize = maxSize;
           arr = new int[maxSize];
       }
   
       /**
        * 存入数据
        */
       public void add(int num) {
           if (isFull()) {
               throw new RuntimeException("Queue is full!");
           }
           arr[rear] = num;
           rear = (rear + 1) % maxSize;
       }
   
       /**
        * 取出数据
        */
       public int push() {
           if (isEmpty()) {
               throw new RuntimeException("Queue is empty!");
           }
           int num = arr[front];
           front = (front + 1) % maxSize;
           return num;
       }
   
       /**
        * 展示所有数据
        */
       public void show() {
           if (isEmpty()) {
               return;
           }
           for (int i = front; i < front + size(); i++) {
               System.out.println(arr[i % maxSize]);
           }
       }
   
       /**
        * 队列长度
        */
       public int size() {
           return (rear + maxSize - front) % maxSize;
       }
   
       /**
        * 是否为空
        */
       private boolean isEmpty() {
           return front == rear;
       }
   
       /**
        * 是否为满
        */
       private boolean isFull() {
           return (rear + 1) % maxSize == front;
       }
   }