• 隊列的介紹
• 數(shù)組模擬隊列的思路
• 模擬隊列代碼實現(xiàn)
• 數(shù)組模擬隊列存在的問題和優(yōu)化
• 數(shù)組模擬環(huán)形隊列思路
• 模擬環(huán)形隊列代碼實現(xiàn)

1. 隊列的介紹

• 隊列是一個有序列表，可以用 數(shù)組 或 鏈表來實現(xiàn)
• 遵循 先進先出 的原則，即：先存入隊列的數(shù)據(jù)，要先取出。后存入的要后取出
• 示意圖（數(shù)組模擬隊列）

image-20220321183514414

2. 數(shù)組模擬隊列的思路分析

• 隊列本身就是有序列表，若使用數(shù)組的結(jié)構(gòu)來存儲隊列的數(shù)據(jù)，其中 maxSize 是隊列的最大容量

• 隊列的輸出、輸入 是分別從前后端來處理的，因此需要 兩個變量 front和rear 分別記錄隊列前后端的下標

  • front 會隨著輸出而改變
  • rear 會隨著輸入而改變
  image-20220321183911022

• 將數(shù)組存入隊列時有兩個步驟：思路分析：

  ① 將尾指針往后移：rear+1

  ② 若 尾指針 rear 小于隊列的最大下標 maxSize-1，則將數(shù)據(jù)存入 rear 所指的 數(shù)據(jù)元素中，否則無法存入數(shù)據(jù)。

  rear == maxSize - 1 :隊列滿

• 出隊列時：

  將頭指針后移：front++, 當front == rear時，隊列為空

3. 模擬隊列代碼實現(xiàn)

//使用數(shù)組模擬隊列-編寫一個 ArrayQueue類
class ArrayQueue{
    private int maxSize; //表示數(shù)組的最大容量
    private int front; //隊列的頭
    private int rear; // 隊列的尾
    private int[] arr; // 該數(shù)組用于存放數(shù)據(jù)，模擬隊列

    //創(chuàng)建隊列的構(gòu)造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize; // 數(shù)組最大容量
        arr = new int[maxSize];
        front = -1;  //初始化，指向隊列頭部.分析出 front是指向隊列頭的前一個位置
        rear = -1;   //初始化，指向隊列尾部數(shù)據(jù)（即就是隊列最后一個數(shù)據(jù)）

    }
    //判斷隊列是否滿
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    //判斷隊列是否為空
    public boolean isEmpty(){
        return rear == front;
    }
    //添加數(shù)據(jù)到隊列
    public void addQueue(int n){
        //判斷隊列是否滿
        if(isFull()){
            System.out.println("隊列滿，不能加入數(shù)據(jù)~");
            return;
        }

        rear++; //讓 rear后移
        arr[rear] = n;
    }
    //獲取隊列的數(shù)據(jù)，出隊列
    public int getQueue(){
        //判斷隊列是否為空
        if(isEmpty()){
            // 通過拋出異常
            throw new RuntimeException("隊列空，不能取數(shù)據(jù)");
        }
        front++;//讓front 后移，開始處于-1
        return arr[front];
    }

    //顯式隊列的所有數(shù)據(jù)
    public void showQueue(){
        //遍歷
        if(isEmpty()){
            System.out.println("隊列空的，沒有數(shù)據(jù)~");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n",i,arr[i]);

        }
    }

    //顯式隊列的頭數(shù)據(jù)，注意不是取出數(shù)據(jù)
    public int headQueue(){
        //判斷
        if(isEmpty()){
            throw new RuntimeException("隊列空，不能取數(shù)據(jù)");
        }
        return arr[front++];
    }
}

• 測試類

public class ArrayQueueDemo {
    public static void main(String[] args) {
        //測試
        //創(chuàng)建一個隊列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' '; //接收用戶輸入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //輸出一個菜單
        while(loop){
            System.out.println("s(show):顯示隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數(shù)據(jù)到隊列");
            System.out.println("g(get):從隊列去除數(shù)據(jù)");
            System.out.println("h(head):查看隊列頭的數(shù)據(jù)");
            key = scanner.next().charAt(0);//接收一個字符
            switch(key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("輸出一個數(shù)：");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的數(shù)據(jù)是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = arrayQueue.headQueue();
                        System.out.printf("隊列頭部的數(shù)據(jù)是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~~");
    }
}

4. 數(shù)組模擬隊列存在問題和優(yōu)化

• 目前數(shù)組使用一次就不能用了，沒有達到服用的效果
• 將這個數(shù)組使用算法，改進成一個 環(huán)形的隊列： 取模%

5. 數(shù)組模擬環(huán)形隊列的思路分析

• 對前面數(shù)組模擬隊列優(yōu)化，充分利用數(shù)組?？梢詫?shù)組看作成一個環(huán)形的（通過取模方式實現(xiàn)）

• 說明

  ① 尾索引的下一個為頭索引時，表示隊列滿：即 將隊列容量空出一個作為約定，

  在判斷隊列滿時需要注意 (rear+1)% maxSize == front時表示隊列滿

  ② rear == front 表示隊列空

• 示意圖：

  image-20220321190818610

• 思路分析

  ① front: 指向隊列的第一個元素，也就是說 arr[front] 就是隊列的第一個元素

  ② rear: 指向隊列的最后一個元素后的一個位置。因為空出一個空間作為約定。 rear 的初始值 = 0；

  ③ 當隊列滿的條件為：(rear + 1) % maxSize = front

  ④ 當隊列為空的條件為：rear == front

  ⑤ 隊列的有效數(shù)據(jù)個數(shù)為：(rear + maxSize - front) % maxSize

  ⑥ 將數(shù)據(jù)存入隊列時: 若隊列未滿，直接加入arr[rear]=n; 然后 rear=(rear+1)%maxSize;

  ⑦ 取出隊列時：若隊列不為空，直接取出一個值value=arr[front],然后 front=(front+1)%maxSize;

6. 數(shù)組模擬環(huán)形隊列的代碼實現(xiàn)

class CircleArray{
    private int maxSize; //表示數(shù)組的最大容量
    //front 變量含義做一個調(diào)整：front 就指向隊列的第一個元素，也就是說 arr[front] 就是隊列的第一個元素
    // front 的初始值 = 0
    private int front ;
    // rear 變量的含義做一個調(diào)整：rear 指向隊列的最后一個元素的后一個位置，因為希望空出一個空間為約定，
    // rear 的初始值 = 0
    private int rear;
    private int[] arr;// 該數(shù)字據(jù)用于存放數(shù)據(jù)，模擬隊列

    public CircleArray(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        //front \ rear 默認為0
    }
    //判斷隊列是否滿
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }
    //判斷隊列是否為空
    public boolean isEmpty(){
        return rear == front;
    }
    //添加數(shù)據(jù)到隊列
    public void addQueue(int n){
        //判斷隊列是否滿
        if(isFull()){
            System.out.println("隊列滿，不能加入數(shù)據(jù)~");
            return;
        }
        //直接將數(shù)據(jù)加入
        arr[rear] = n;
        //將rear 后移，這里必須考慮取模
        rear = (rear + 1) % maxSize;
    }

    //獲取隊列的數(shù)據(jù)，出隊列
    public int getQueue(){
        //判斷是否為空
        if(isEmpty()){
            //通過拋出異常
            throw new RuntimeException("隊列空，不能取數(shù)據(jù)");
        }
        // 這里需要分析出 front 是指向隊列的第一個元素
        //1. 先把 front 對應的值保留到一個臨時變量
        //2. 將 front 后移,考慮取模
        //3. 將臨時保存的變量返回
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    //顯示隊列的所有數(shù)據(jù)
    public void showQueue(){
        //遍歷
        if(isEmpty()){
            System.out.println("隊列空的，沒有數(shù)據(jù)~");
            return;
        }
        //思路：從front 開始遍歷，遍歷多少個元素
        for(int i = front; i < front + size();i++){
            System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]); //環(huán)形
        }

    }
    //求出當前隊列有效數(shù)據(jù)的個數(shù)
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }

    //顯示隊列的頭數(shù)據(jù)，注意不是取出數(shù)據(jù)
    public int headQueue(){
        //判斷
        if(isEmpty()){
            throw new RuntimeException("隊列空的，沒有數(shù)據(jù)~");
        }
        return arr[front];
    }
}

• 測試類

public class CircleArrayQueue {
    public static void main(String[] args) {
        //測試
        System.out.println("測試數(shù)據(jù)模擬環(huán)形隊列的案例~~ ");

        CircleArray arrayQueue = new CircleArray(4); //說明設(shè)置4，其隊列的有效數(shù)據(jù)最大是3，約定空出一個空間
        char key = ' '; //接收用戶輸入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //輸出一個菜單
        while(loop){
            System.out.println("s(show):顯示隊列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加數(shù)據(jù)到隊列");
            System.out.println("g(get):從隊列去除數(shù)據(jù)");
            System.out.println("h(head):查看隊列頭的數(shù)據(jù)");
            key = scanner.next().charAt(0);//接收一個字符
            switch(key){
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("輸出一個數(shù)：");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的數(shù)據(jù)是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = arrayQueue.headQueue();
                        System.out.printf("隊列頭部的數(shù)據(jù)是%d\n",res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~~");
    }
}