【小白學演算法】3. 循環隊列

在上一章中，使用了數組模擬了隊列。但是留下的問題是，把數據取完後，再往裡加數據就不行了。

一、假溢出

這是因為數組的末尾已經被佔用了，入隊會繼續在數組後面增加，於是產生數組越界。
但是實際上，數組裡是有空閑位置的，這種也可以叫「假溢出」。

為了解決「假溢出」的問題，於是乎有了循環隊列。

既然數組後面滿了，頭部有空，那繼續加進來的元素從頭開始放即可。

接著上圖，這時候有a6入隊，於是rear的下標指向a6的下一個元素位置，看起來沒什麼問題。

但是繼續有新的元素a7入隊的時候，因為front一直沒變，這時候rear指針跟front就重合了，也就是說此時front=rear。

可是在上一章的程式碼里，我們是用front=rear來判斷是否為空數組的。

    // 判斷隊列是否為空
    public boolean isEmpty() {
        return rear == front;
    }

現在是相等了，條件滿足，但是數組是滿的。

二、循環隊列判斷是空是滿

這種情況看起來確實比較辣手，那如果不讓這種情況出現不就可以了么？

假設，我們讓數組始終保留一個元素空間，也就是讓rear指向隊列中最後一個元素的後一個位置。
比如，當a6放入之後，此時就當做隊列已經滿了，這樣的話就不會出現上述的情況了。

為了實現這種思路，front也需要做調整。在上一章中，front初始位置是指在了隊頭元素的前一個，現在我們讓它就指在
第一個元素。隊列的最大尺寸還是maxSize，那麼，現在判斷隊列滿的條件就可以是這樣：(rear+1)%maxSize = front

驗證一下，下面的2種隊列滿情況：

左圖：隊列中，maxSize=5，front=0，rear=4，判斷（4+1）% 5=0=front，隊列已滿
右圖：隊列中，maxSize=5，front=2，rear=1，判斷（1+1）% 5=2=front，隊列已滿

繼續驗證一下，隊列沒滿的情況：

隊列中，maxSize=5，front=2，rear=0，判斷（0+1）% 5=1≠front，隊列未滿

三、循環隊列的長度計算

隊列的長度，也就是說隊列中實際存了多少個元素。
此時需要考慮rear與front之間的三種情況：

rear=front
rear>front
rear<front

第一種自然都清楚，隊列為空。

第二種，rear>front，此時隊列的長度為：rear-front

第三種，rear<front，比較複雜些。
隊列長度分為2段：一段是maxSize-front，另一段則是：0+rear(結合右圖理解)。故此時隊列總長度為兩段相加：rear-front+maxSize

所以隊列長度的通用計算公式為：（rear-front+maxSize）% maxSize

四、程式碼實現

既然現在隊列是滿是空的判斷條件有了，隊列長度也能計算出來了，那麼程式碼就好改造了（基於上一章），變成循環隊列。

package circle;

import java.util.Scanner;

public class CircleArrayQueue {
    public static void main(String[] args) {
        System.out.println("-----測試循環隊列-----");
        // 創建一個隊列
        CircleArray circleArray = new CircleArray(4);
        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): 添加數據到隊列");
            System.out.println("g(get): 從隊列取出數據");
            System.out.println("h(head): 顯示隊首的數據");
            key = scanner.next().charAt(0); // 接收一個字元
            switch (key) {
                case 's':
                    circleArray.showQueue();
                    break;
                case 'a':
                    System.out.println("請要添加的數");
                    int value = scanner.nextInt();
                    circleArray.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = circleArray.getQueue();
                        System.out.printf("取出的數據是：%d", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int headValue = circleArray.showHeadQueue();
                        System.out.printf("隊首數據是：%d", headValue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        System.out.println("退出程式");
    }
}
class CircleArray {
    //表示數組最大容量
    private int maxSize;
    // 隊列頭，由之前調整為指向隊列第一個元素
    private int front;
    // 隊列尾，由之前調整為指向隊列最後一個元素的後一個位置，為了空出一個元素位置
    private int rear;
    // 用於存放數據的數組
    private int[] arr;

    // 構造器
    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }

    // 判斷隊列是否已經存滿
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    // 判斷隊列是否為空
    public boolean isEmpty() {
        return rear == front;
    }

    // 添加數據到隊列
    public void addQueue(int num) {
        // 判斷隊列是否滿了
        if (isFull()) {
            System.out.println("隊列已滿，不可加入數據");
            return;
        }
        arr[rear] = num;
        // 將rear後移，要考慮取模
        rear = (rear + 1) % maxSize;
    }

    // 拿出隊列數據
    public int getQueue() {
        // 判斷隊列是否空
        if (isEmpty()) {
            // 拋出異常
            throw new RuntimeException("隊列為空，不可取數據");
        }
        int tempValue = arr[front];
        front = (front + 1) % maxSize; //也要考慮取模，防止front不停的增加，導致越界
        return tempValue;
    }

    // 顯示隊列所有數據
    public void showQueue() {
        // 遍歷
        if (isEmpty()) {
            System.out.println("隊列為空");
            return;
        }
        // 從front開始遍歷，遍歷多少個實際存的元素即可
        for (int i = front; i < front + CircleQueueSize(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }

    }

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

    // 顯示隊里的隊首數據
    public int showHeadQueue() {
        if (isEmpty()) {
            // 拋出異常
            throw new RuntimeException("隊列為空，不可取數據");
        }
        return arr[front];
    }
}

重點的改動在於取模。

Tags: 把蘋果咬哭的不規律日常數據結構與演算法