# 資料結構&演算法 4. 堆疊(Stack)

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

## 關於堆疊(Stack)本篇將討論以下幾個項目
:::info
### 1. 什麼是堆疊(Stack)？
### 2. 如何以 Array (陣列)實作堆疊(Stack)？
### 3. 如何以 Linked List (鏈結串列、鏈表)實作堆疊(Stack)？
:::

---
## 測試環境：
> OS：Windows 10
> IDE：Visual Studio 2019

---
## 1. 什麼是堆疊(Stack)？
### 簡單來說，堆疊(Stack)就是個後進先出的集合
相較於 Array & LinkedList 操作比較不受限，Stack 所受限制反而有利於特定情境，以避免使用上不受限造成的錯誤

---
## 2. 如何以 Array (陣列)實作堆疊(Stack)？
### 接下來實作 Stack 的 Push(加入資料) & Pop(取出資料)
#### 範例：

    public class StackByArray<T>
        where T : struct
    {
        private readonly int _size;
        private readonly T[] container;
        // 最後一個 item 的 Index，-1 表示容器內為空
        private int lastItemIndex = -1;
        public int ItemCount => lastItemIndex + 1;

        public StackByArray(int size)
        {
            _size = size;
            container = new T[size];
        }

        // 加入資料
        public bool Push(T item)
        {
            if (ItemCount == _size)
                return false;

            lastItemIndex++;
            container[lastItemIndex] = item;
            return true;
        }

        // 取出資料
        public T? Pop()
        {
            if (lastItemIndex == -1)
                return null;

            T item = container[lastItemIndex];
            lastItemIndex--;

            return item;
        }
    }

#### 操作 & 結果


此範例容量無法動態擴展
> Push 超過容量上限時回傳 Fail
> Pop 遇到 stack 內沒有資料時回傳 null

Array 沒有 Push or Pop 之外的搬移動作，所以兩者的時間複雜度皆為：

時間複雜度：O(1)

動態擴展容量的情況

> Pop 不變
> Push 遇到容量不足時就 new 一個更大容量的 Array，並且將資料搬移過去，多了搬移的動作

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

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

---
## 3. 如何以 Linked List (鏈結串列、鏈表)實作堆疊(Stack)？
### 接下來實作 Stack 的 Push(加入資料) & Pop(取出資料)
#### 範例：

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

        // 加入資料
        public bool Push(T item)
        {
            linkedList.AddFirst(item);

            return true;
        }

        // 取出資料
        public T? Pop()
        {
            var firstItem = linkedList.First?.Value;

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

            return firstItem;
        }
    }

#### 操作 & 結果


LinkedList 本身容量限制在於硬體，但相較於 Array 多紀錄了指標，需要使用更多的記憶體空間，但也少了搬移的問題，Push & Pop 時間複雜度皆為：

時間複雜度：O(1)

---
## 總結
### 本篇使用 Array 跟 Linked List 來實作 Stack，相信在讀完本篇後應該對 Stack 更熟悉了一些，也許某天會遇到適合的情況能用得上，當然還是建議直接使用 .NET 提供的 [Stack Class](https://docs.microsoft.com/zh-tw/dotnet/api/system.collections.stack?view=netframework-4.8) 即可，沒必要自己造輪子。

### 另外，可以對比一下本篇實作 Stack 情況下的時間複雜度，與[前篇 Array & Linked List](https://hackmd.io/@WayneCheng/B1Je7I5OP) 所介紹的時間複雜度的差異，同樣類別不同情況下該如何分析時間複雜度

---

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