# 佇列(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會指向最後一個元素的後一個位置。