iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 2
2
Software Development

從零開始土炮MQ系列 第 2

二、基本的 queue (1) - Line Queue & Circle Queue

1. Queue

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

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

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

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

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

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

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

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

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

通常,會把資源放入 Queue 的動作,稱為 PushEnqueue。反之,從資源離開 Queue 的動作,稱為 PopDequeue

https://ithelp.ithome.com.tw/upload/images/20190918/20107551JdaIq3Z2TZ.png

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;
    }
}

上一篇
一、前言
下一篇
二、基本的 queue (2) - Priority Queue
系列文
從零開始土炮MQ30

尚未有邦友留言

立即登入留言