資料結構 (C#)：堆疊實作與字串反轉應用

C# 堆疊 (Stack) 實作：以單向鏈結串列為底層、後進先出 (LIFO) 語意封裝

堆疊特性：僅操作頂端，Push 壓入、Pop 彈出、Top 取頂。適用函式呼叫堆疊、運算式求值、回溯演算法等場景。

一、Stack 類別完整程式碼

namespace Xianfen.Net.DataStructure
{
    public class Stack<T>
    {
        protected SingleLinkedList<T> m_List;

        public int Count { get { return m_List.Count; } }
        public bool IsEmpty { get { return m_List.IsEmpty; } }

        public Stack() { m_List = new SingleLinkedList<T>(); }
        public Stack(T t) { m_List = new SingleLinkedList<T>(t); }

        // 彈出：取得並移除尾端 (堆疊頂端)
        public T Pop()
        {
            T t = m_List.GetTail();
            m_List.RemoveTail();
            return t;
        }

        // 取頂端不移除
        public T Top() { return m_List.GetTail(); }

        // 壓入：加入尾端
        public void Push(T t) { m_List.AddTail(t); }
    }
}

二、應用範例：字串反轉

char[] ch = "hello world!".ToCharArray();
Stack<char> s = new Stack<char>();

foreach (char c in ch) s.Push(c);

int idx = 0;
while (!s.IsEmpty)
{
    ch[idx++] = s.Pop();
}

Console.WriteLine(new string(ch)); // 輸出: !dlrow olleh

三、設計對比

四、結語

堆疊與佇列皆以單向鏈結串列為底層，僅差異於操作端點與語意。實務開發中 .NET 內建 System.Collections.Generic.Queue<T>、Stack<T> 效能經優化，建議優先使用框架提供的版本。