5. 隊列(Queue)

關於隊列(Queue)本篇將討論以下幾個項目

1. 什麼是隊列(Queue)？

2. 如何以 Array (陣列)實作隊列(Queue)？

3. 如何以循環 Array (陣列)實作隊列(Queue)？

4. 如何以 Linked List (鏈結串列、鏈表)實作隊列(Queue)？

5. Array & Linked List 實作比較

測試環境：

OS：Windows 10
IDE：Visual Studio 2019

1. 什麼是隊列(Queue)？

簡單來說，隊列(Queue)就是個先進先出的集合

如同 Stack，Queue 也是個操作受限的集合，各種變形常見於各類底層服務，如電腦中等待 CPU 處理的各種待辦

2. 如何以 Array (陣列)實作隊列(Queue)？

接下來以 Array 實作 Queue 的 Enqueue(加入資料) & Dequeue(取出資料)

範例：

    public class QueueByArray
    {
        private int[] _IntArray;
        private int _Size = 0;
        private int _HeadIndex = 0;
        private int _TailIndex = 0;

        public QueueByArray(int arraySize)
        {
            _IntArray = new int[arraySize];
            _Size = arraySize;
        }

        public bool Enqueue(int value)
        {
            // _IntArray 已滿，無法再加入資料
            if (_HeadIndex == 0 && _TailIndex == _Size) return false;

            // _IntArray 後方已達容量上限，但前方有空位，需要將所有資料往前搬移
            if (_TailIndex == _Size)
            {
                for (var i = _HeadIndex; i < _TailIndex; ++i)
                {
                    _IntArray[i - _HeadIndex] = _IntArray[i];
                }

                _TailIndex = _TailIndex - _HeadIndex;
                _HeadIndex = 0;
            }

            _IntArray[_TailIndex] = value;

            _TailIndex++;

            return true;
        }

        public int Dequeue()
        {
            // _IntArray 內沒有資料
            if (_HeadIndex == _TailIndex) return -1;

            var result = _IntArray[_HeadIndex];

            _HeadIndex++;

            return result;
        }
    }

操作 & 結果

程式實際上是這樣運作的

1. 沒有資料的時候 _HeadIndex & _TialIndex 都在第一個位置

2. Enqueue 時 _HeadIndex 不變，_TialIndex + 1

3. 再次 Enqueue 時 _HeadIndex 不變，_TialIndex + 1

4. Dequeue 時 _HeadIndex + 1，_TialIndex 不變

由上圖的步驟可以看出來 _HeadIndex & _TialIndex 都在不斷向後移，到最後儘管前面還有空間可以放置資料，卻因為 _HeadIndex & _TialIndex 的位置而無法使用

為了避免明明有空間卻無法 Enqueue 的狀況，我們可以在 _TialIndex 移到最後時判斷 _HeadIndex 的位置是否可以往前搬移，若 _HeadIndex 前方有 n 個空位，則將所有資料全部向前位移 n 個位置，此時時間複雜度：

Dequeue
    時間複雜度：O(1)

Enqueue
    // 沒有搬移的情況下
    最佳情況時間複雜度：O(1)

    // 搬移的情況下
    最壞情況時間複雜度：O(n)

    平均情況時間複雜度：O(1)

3. 如何以循環 Array (陣列)實作隊列(Queue)？

接下來以循環 Array 實作 Queue 的 Enqueue(加入資料) & Dequeue(取出資料)

範例：

    public class QueueByCircularArray
    {
        private int[] _IntArray;
        private int _ArraySize = 0;
        private int _DataSize = 0;
        private int _HeadIndex = 0;
        private int _TailIndex = 0;

        public QueueByCircularArray(int arraySize)
        {
            _IntArray = new int[arraySize];
            _ArraySize = arraySize;
        }

        public bool Enqueue(int value)
        {
            // Array 已經滿了
            if (_ArraySize == _DataSize) return false;

            _IntArray[_TailIndex] = value;
            _TailIndex = (_TailIndex + 1) % _ArraySize;
            _DataSize++;

            return true;
        }

        public int Dequeue()
        {
            // Array 內沒有任何資料
            if (_DataSize == 0) return -1;

            var result = _IntArray[_HeadIndex];

            _HeadIndex = (_HeadIndex + 1) % _ArraySize;
            _DataSize--;

            return result;
        }
    }

操作 & 結果

程式實際上是這樣運作的

1. _HeadIndex 因為前面已經取出兩次資料所以在第三個位置，而 _TailIndex 在最後一個位置

2. Enqueue 時 _HeadIndex 不變，_TialIndex 則是因為前方還有兩個空位直接回到第一個位置，以循環的方式將資料放置到 queue 中

由上圖的步驟可以看出來，由於是循環的方式在指定 _HeadIndex & _TialIndex，比起原本的方式少了搬移的動作，所以此時的時間複雜度：

Dequeue
    時間複雜度：O(1)

Enqueue
    時間複雜度：O(1)

4. 如何以 Linked List (鏈結串列、鏈表)實作隊列(Queue)？

接下來以 Linked List 實作 Queue 的 Enqueue(加入資料) & Dequeue(取出資料)

範例：

    public class QueueByLinkedlist<T>
        where T : struct
    {
        private LinkedList<T> linkedList { get; set; } = new LinkedList<T>();

        public bool Enqueue(T value)
        {
            linkedList.AddLast(value);
            return true;
        }

        public T? Dequeue()
        {
            var firstItem = linkedList.First?.Value;

            // 如果有值，則取出後刪除
            if (firstItem != null)
                linkedList.RemoveFirst();

            return firstItem;
        }
    }

操作 & 結果

比起 Array 來說，Linked List 實作起來相當簡單，且沒有容量限制，時間複雜度：

Dequeue
    時間複雜度：O(1)

Enqueue
    時間複雜度：O(1)

5. Array & Linked List 實作比較

Linked List 容量限制在硬體上，對於程式來說就是個容量沒有限制的 Queue

實務上處理 Queue 的服務的資源並非無限，單位時間內能夠處理的量是固定的，通常待處理項目會有 Timeout 的問題，無法無限制等待下去，所以 Array 有限容量反而會是個更好的選擇，在超出容量上限時直接不處理，避免還要等待到 Timeout 才知道處理失敗

總結

本篇使用 Array 跟 Linked List 來實作 Queue，也從 Array 的兩種實作中可以看出兩者在時間複雜度的差異，實作的難度差異不大，但在分析過時間複雜度之後就知道哪種方法會更好了。

實務上遇到的需求遠比範例複雜得多，本篇沒有對於複雜情境多做說明，不過對應複雜情境可以使用像是 RabbitMQ 來處理。

新手上路，若有錯誤還請告知，謝謝