4. 堆疊(Stack)

關於堆疊(Stack)本篇將討論以下幾個項目

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 即可，沒必要自己造輪子。

另外，可以對比一下本篇實作 Stack 情況下的時間複雜度，與前篇 Array & Linked List 所介紹的時間複雜度的差異，同樣類別不同情況下該如何分析時間複雜度。

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