1. Queue

首先，我們先來聊聊 Queue 的基本概念。

還記得先前提到，Queue 具有暫存緩衝與它先進先出的兩種特性嗎？我們舉個與 Queue 概念相進的現實例子。

假設今天是張學友的簽名握手會，時間是中午一點到下午三點，共兩小時。早上八點開放排隊，只有在隊列中的人才有資格參與活動。(先忽略中途放棄、與插隊的情況。)

下午一點一到，張學友開始簽名會。排在最前面的歌迷，理所當然的第一個與張學友簽名握手，離開後，換下一位歌迷。
還沒輪到的歌迷，只能在隊列中，持續等待到輪到自己的時候。

到了三點，雖然還有許多歌迷在排隊，但張學友礙於行程的規劃，只能準時結束簽名會。沒能要到簽名的歌迷，只能乖乖的離去。

在上面的例子，就可以看 Queue 的幾個特性。

• 先進先出：最前面的歌迷，最早與張學友簽名握手，其他次之。
• 暫存緩衝：不管歌迷有多少人，多早到，都要進隊列，等待主角的到來。
• 資源調配：時間資源有限，不是進入隊列的歌迷，都有機會拿到簽名。

從上面的例子，可以將 Queue 想像為一個線性的空隊列，當資源進入 Queue (歌迷開始排隊)，就會產生頭(Front)、尾(Rear) 的概念。

當資源不停的進入，Rear 就會不停的往後移動。只要沒有資源離開 Queue ，Front 都是固定不動的。反之，只要有資源開始離開，Front 就會往下一個資源移動。

通常，會把資源放入 Queue 的動作，稱為 Push 或 Enqueue。反之，從資源離開 Queue 的動作，稱為 Pop 或 Dequeue。

2. Line Queue

最基本方式，就是事前先宣告 Queue 一次最多接收多少個資源。

下面的例子，沒額外處理進入的資源超過 Queue 限制的情況。當然，放入的資源超過 Queue 可接收的限制，一定會造成問題。就像客運明明只能上 15 個人，客運公司不小心超賣 2 張，第 16、17 人上不了客運，一定會造成預期外的事件。

但因為這不是我們要討論的重點，就先放在一邊。

第一種 Queue 的處理方式，當 Queue 之中，最前面的資源離開 Queue 後，後面的資源會自己向前遞補，讓資源主動移到 Front 。

public class Queue 
{
    private const int MaxSize = 20;
    private int[] _buffer = new int[MaxSize];
    private int _index = 0;
    
    public void Enqueue (int item)
    {
        _buffer[_index] = item;
        _index++;
    }

    public bool IsEmpty { get { return _index == 0; } }

    public int Dequeue ()
    {
        int item = _buffer[0];
        for (int i = 0; i <= _index; i++) {
            _buffer[i] = _buffer[i + 1];
        }
        //  避免最後一位沒有初始化
        if (_index == MaxSize - 1)
            _buffer[_index] = 0;
        _index--;
        return item;
    }
}

2. Circle Queue

後來發現，每次移動資源的成本過於昂貴，若資源量少，可能還看不出差異。但資源數量成千上萬時，所耗費成本，就相當可觀。

要解決上面的問題，那是不是有方法，在不移動資料本身位置的時候，一樣可以識別出 Front 與 Rear 的位置？

既然資源本身不能移動，那麼，利用兩組指標，分別指向 Front 與 Read 位置不就可了。當資源 Push 或 Pop 時，指標進行對應的移動即可。

這麼一來，就可以大幅減少移動資源造成的耗損成本。

但實作上發現，單純只是更新指標指向資源的話，可能會不小心讓資料跑出 Queue 的可控範圍，所以必須在資源放入 Queue 時，進行控制。

最後，會發現迭代完成的 Queue ，就是 circle 的架構，又被叫作 Circle Queue

public class CircleQueue
{
    private const int MaxSize = 20;
    private int[] _buffer = new int[MaxSize];
    private int _front = 0;
    private int _rear = 0;

    public void Enqueue(int item)
    {
        _buffer[_rear] = item;
        _rear++;
    }

    public bool IsEmpty
    {
        get { return _front == _rear; }
    }

    public int Dequeue()
    {
        int item = _buffer[_front];
        //  初始化
        _buffer[_front] = 0;
        _front++;
        return item;
    }
}