關於堆疊(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)
