# 資料結構&演算法 5. 隊列(Queue)

###### tags: `資料結構&演算法`

## 關於隊列(Queue)本篇將討論以下幾個項目
:::info
### 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)？
### 接下來實作 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 的 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 的 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 跟 Array 不同，容量限制在硬體上，但對於程式來說幾乎就是個容量無限大的 Queue

### 但實務上處理 Queue 的資源有限，在大多時候待處理項目會有 Timeout 的問題，無法一直等待下去，所以 Array 有限容量反而會是個更好的選擇，在超出容量上限時直接不處理，避免還要等待到 Timeout 才知道處理失敗

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

### 實務上遇到的需求遠比範例複雜得多，本篇沒有對於複雜情境多做說明，不過對應複雜情境可以使用像是 [RabbitMQ](https://www.rabbitmq.com/) 來處理

---

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