佇列(Queue)與環形佇列

使用場景: 排隊買票

特徵

1. 先進先出(FIFO)
2. 有序列表，可以用陣列或連結串列來實現。
3. Queue兩個指針：rear 佇列的尾部(含)、front 佇列的頭部(不含)。
4. 新增數據時，front不動rear動；刪除數據時，rear不動front動 => 由尾端加入數據，由頭部取出。

我們可以以排隊買票為例，將排隊的隊列視作Queue，先排隊的人先買票，後到的人排在後面等待買票，並且先買票的人買完票之後就離開隊伍；我們將第一個買票的人稱之為front，隊伍最後一個等待買票的人為rear。

當1號買完票離開換2號買票時，此時的front變為2號。

當又有下一個人(5號)要買票，此時rear從4號變到5號身上。

因此我們可以得出，當新增數據時，front不動rear動；刪除數據時，rear不動front動。

陣列模擬佇列

當我們將數據存入佇列時稱為addQueue，addQueue的處理須要有兩個步驟：

1. 將尾指針往後移：rear+1，當 front == rear 為空。
2. 若尾指針 rear < maxSize-1 則將數據存入rear所指的陣列元素中；若 rear == maxSize-1 為佇列已滿。

代碼實現

class ArrayQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] arr;

    //創建佇列的構造函數
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1;  //指向佇列頭部,分析出front是指向佇列頭部的前一個位置
        rear = -1; //指向佇列尾部,指向佇列尾部的數據(佇列最後一個數據)
    }

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

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

    //添加數據到佇列
    public void addQueue(int n) {
        //判斷佇列是否滿
        if(isFull()){
            System.out.println("佇列已滿,不能加入數據");
            return;
        }
        rear++; //讓rear後移
        arr[rear] = n;
    }

    //獲取佇列數據出佇列
    public int getQueue() {
        //判斷佇列是否空
        if(isEmpty()){
            throw new RuntimeException("佇列為空,無值可取"); //throw本身造成代碼return 不須另外寫return
        }
        front++; //讓rear後移
        return arr[front];
    }

    //顯示佇列數據
    public void showQueue() {
        if(isEmpty()){
            System.out.println("佇列空的,沒有數據");
            return;
        }
        for(int i=0;i<arr.length;i++){
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }
}

public class ArrayQueueDemo {
    public static void main(String[] args){
        ArrayQueue queue = new ArrayQueue(5);
        char key = ' ';
        Scanner sc = new Scanner(System.in);
        boolean loop = true;
        
        while(loop){
            System.out.println("s(show)顯示佇列 | e(exit)退出程序 | a(add)添加數據到佇列 | g(get)從佇列取出數據 | h(head)查看佇列頭的數據");
            key = sc.next().charAt(0);
            switch(key){

                case 's':
                    queue.showQueue();
                    break;

                case 'e':
                    sc.close();
                    loop = false;
                    break;

                case 'a':
                    System.out.println("請輸入要添加的數據:");
                    int value = sc.nextInt();
                    queue.addQueue(value);
                    break;

                case 'g':
                    try {
                        int result = queue.getQueue();
                        System.out.printf("取出的數據是 %d\n",result);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;

                case 'h':
                    try {
                        int result = queue.headQueue();
                        System.out.printf("佇列頭的數據是 %d\n",result);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
            }

            
        }
        System.out.println("程序已結束~");
}

目前使用會遇到的困難為：佇列使用一次就不能再用，當我將數據取出，前端明明還有空位但想新增數據卻被告知佇列已滿。

因此需要優化，將之改為環形佇列。

陣列模擬環形佇列

思路分析

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

使用環形佇列後，數據可以一直刪減、新增直到沒有空餘的位置，形成一個環狀的結構，因此不會浪費多餘的空間。

---

舉個簡單的例子來加深印象好了：

當我今天宣告一個環形佇列 MaxSize 為4，那就代表我這個佇列有效數據最大是3，因為有一個儲存單元要預留下來判斷是否為空還是滿。

添加數據 10,20,30
arr[0] = 10 , arr[1] = 20 , arr[2] = 30

取出數據，則只剩下
arr[1] = 20 , arr[2] = 30

新增數據 40
arr[1] = 20 , arr[2] = 30 , arr[3] = 40

繼續取出 20 和 30
arr[3]=40

再去新增數據 50,60
arr[3] = 40 , arr[0] = 50 , arr[1] = 60

再把 40 取出，加入70 會變為
arr[0] = 50 , arr[1] = 60 , arr[2] = 70

---

小整理

佇列

• front的初始值 = -1 , rear的初始值 = -1
• 判斷佇列為空 rear == front
• 判斷佇列為滿 rear = maxSize -1

環形佇列

• front的初始值 = 0 , rear的初始值 = 0
• 需預留一個儲存單元來判斷佇列是否為空還是滿
• 判斷佇列為空 rear == front
• 判斷佇列為滿 (rear+1) % maxSize == front
• 判斷佇列的有效數據個數 (rear + maxSzie - front) % maxSize
  front = 0
  rear = 5
  maxSize = 7
  (5+7-0) % 7 = 5 ，共有五個有效數據。
  為什麼不是6？
  因為rear會指向最後一個元素的後一個位置。