並發數據結構：無鎖棧的設計與實現

在探討並發棧之前，先回顧非線程安全的棧結構。棧是一種線性數據結構，僅能在一端存取數據，遵循後進先出（LIFO）原則，猶如餐廳疊放的盤子。

棧的兩種經典實現

數組實現

ArrayStack<T> 維護一個動態數組 array 與棧頂索引 topOfStack。擴容時數組加倍，雖單次 Push 為 O(N)，但攤銷後平均仍為 O(1)。默認容量 16（.NET 內建為 4），大內存時代 16 更合理。

public class ArrayStack<T>
{
    private T[] array;
    private int topOfStack;
    private const int defaultCapacity = 16;
    // ... Push/Pop/Peek/Count 實現
}

鏈表實現

ListStack<T> 僅需維護棧頂節點 topOfStack，額外空間僅為節點引用。所有操作均為嚴格 O(1)。

public class ListStack<T>
{
    private ListNode<T> topOfStack;
    // ... Push/Pop/Peek 實現
    class ListNode<T> { internal T item; internal ListNode<T> next; }
}

兩者時空權衡：數組訪問局部性好、擴容少時更快；鏈表無擴容、空間精確。若能準確預估容量，數組優勢明顯。

Lock-Free 棧：基於 CAS 的鏈表實現

CAS 僅能交換 64 位值，數組實現難以原子化，故採用鏈表。關鍵在於用 CAS 原子更新棧頂指針。

public class LockFreeStack<T>
{
    private ListNode<T> topOfStack;

    public void Push(T item)
    {
        var newTop = new ListNode<T>(item);
        ListNode<T> oldTop;
        do
        {
            oldTop = topOfStack;
            newTop.next = oldTop;
        }
        while (Interlocked.CompareExchange<ListNode<T>>(ref topOfStack, newTop, oldTop) != oldTop);
    }

    public bool TryPop(out T result)
    {
        ListNode<T> oldTop, newTop;
        do
        {
            oldTop = topOfStack;
            if (oldTop == null) { result = default(T); return false; }
            newTop = oldTop.next;
        }
        while (Interlocked.CompareExchange<ListNode<T>>(ref topOfStack, newTop, oldTop) != oldTop);
        result = oldTop.item;
        return true;
    }
    // TryPeek 與 ListNode 定義略
}

ABA 問題深度剖析

CAS 比較的是內存地址。C/C++ 手動內存管理下，釋放後重新分配可能復用同一地址，導致 ABA 問題。.NET 有 GC，托管堆指針 NextObjPtr 單調遞增，配合分代回收、標記清除壓縮，極大降低 ABA 風險：

• TryPop 無內存分配/回收，僅移動現有對象引用，地址不變，無 ABA。
• Push 僅分配新對象，不刪除舊對象，舊對象交給 GC，無 ABA。
• 交替執行時理論上可能發生，但極難重現。.NET ConcurrentStack<T> 與 Java 採用相同實現，業界普遍認為在 GC 環境下可接受。

性能特徵

• 輕/中度爭用：CAS 多數首次成功，爭用僅多幾次循環迭代，無線程掛起/上下文切換，比鎖快 3~4 倍。
• 高度爭用：鎖算法反而吞吐更高，因阻塞線程停止爭用，避免擴散。但此場景罕見，通常意味著算法需重設計以減少共享數據。
• 內存分配/回收（GC 壓力）是高爭用下的性能瓶頸。

下一步將引入 SpinLock 構建更優的並發棧。