C# 泛型順序棧 (SeqStack) 完整實現與解析

棧 (Stack) 數據結構基礎

棧是**限制在表尾進行插入/刪除**的線性表，遵循 **LIFO (後進先出)** 原則：

• 棧頂：允許操作的一端（數組高索引端）。
• 棧底：固定端（數組索引 0）。
• 生活類比：洗碗疊盤子（入棧）、取用從最上層拿（出棧）。

接口設計：IStack<T>

繼承通用數據結構接口 IDS<T>（Count/IsEmpty/Clear），新增棧專有操作：

public interface IStack : IDS {
    void Push(T item);   // 入棧
    T Pop();             // 出棧（移除並返回頂部元素）
    T GetTop();          // 取棧頂元素（不移除）
}

順序棧實現：SeqStack<T>

基於**動態數組**實現，封裝核心字段：

private T[] data;      // 存儲數據
private int maxSize;   // 容量上限
private int top;       // 棧頂指針，-1 表示空棧

構造函數

public SeqStack() : this(10) { } // 默認容量 10

public SeqStack(int size) {
    data = new T[size];
    maxSize = size;
    top = -1;
}

核心操作實現

入棧 Push

public void Push(T item) {
    if (top == maxSize - 1) {
        Console.WriteLine("棧已滿");
        return; // 或拋出異常/擴容
    }
    data[++top] = item; // 先遞增指針，再賦值
}

出棧 Pop

public T Pop() {
    if (top == -1) {
        Console.WriteLine("棧為空");
        return default(T);
    }
    return data[top--]; // 先取值，後遞減指針
}

取棧頂 GetTop

public T GetTop() {
    if (top == -1) {
        Console.WriteLine("棧為空!");
        return default(T);
    }
    return data[top];
}

輔助屬性與接口實現

// 判滿
public bool IsFull => top == maxSize - 1;

// IDS 成員
public int Count => top + 1;

public void Clear() => top = -1;

public bool IsEmpty => top == -1;

// 索引器（僅供調試/遍歷，破壞封裝慎用）
public T this[uint index] {
    get => data[index];
    set => data[index] = value;
}

完整代碼結構

namespace DataStructures {
    public interface IDS {
        int Count { get; }
        void Clear();
        bool IsEmpty { get; }
    }

    public interface IStack : IDS {
        void Push(T item);
        T Pop();
        T GetTop();
    }

    public class SeqStack : IStack {
        // 字段、構造函數、屬性、Push/Pop/GetTop、IDS 實現
        // 見上文完整實現
    }
}

測試用例

var stack = new SeqStack(3);
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine(stack.IsFull);   // True
Console.WriteLine(stack.GetTop()); // 3
Console.WriteLine(stack.Pop());    // 3
Console.WriteLine(stack.Count);    // 2
stack.Clear();
Console.WriteLine(stack.IsEmpty);  // True

擴展方向與生產級建議

• 動態擴容：滿時分配 2x 新數組 Array.Copy 遷移（參考 List<T> 實現）。
• 異常代替輸出：ThrowHelper.ThrowInvalidOperationException() 替代 Console.WriteLine。
• 實現 IEnumerable<T>：支持 foreach 遍歷（從棧頂到棧底）。
• 線程安全版本：ConcurrentStack<T> (System.Collections.Concurrent) 已提供無鎖實現。
• 避免公開索引器：破壞 LIFO 語義，僅調試用。

對比：System.Collections.Generic.Stack<T>