Treiber 無鎖堆疊（the Treiber lock-free stack）
/ TRY-ber /
Treiber 堆疊由 R. Kent Treiber 於 1986 年提出，是最簡單的真實無鎖資料結構，也是人人最先學的標準範例。它是一個後進先出（LIFO）堆疊——push 加到頂端、pop 從頂端移除——完全由單一原子 head 指標加上 CAS 重試迴圈構成，到處都沒有鎖。這裡的「堆疊」指 LIFO 資料結構，不是記憶體中的呼叫堆疊區段。
它這樣運作。堆疊是一個鏈結串列，head 是指向頂端節點的原子指標。要 push 一個新節點 n：把目前的 head 讀進 old，設 n->next = old，再把 head 用 CAS 從 old 換成 n。若 CAS 成功，n 現在就是頂端；若這中間有別的執行緒 push 或 pop，head 不再等於 old，CAS 失敗，你就從最新的 head 重試。要 pop：把 head 讀進 old，讀它的後繼 next = old->next，再把 head 用 CAS 從 old 換成 next；成功時你就解開了舊頂端、可以回傳它。兩個操作都只是把「讀取—計算—CAS」骨架套到一個指標上，這就是這個結構為何如此小巧、如此常被拿來教學。
而 Treiber 堆疊正是 ABA 問題與記憶體回收問題第一次咬到初學者的地方。pop 操作會讀 old->next，但在那次讀取與 CAS 之間，另一個執行緒可能彈出並釋放 old 所指的那個節點——於是解參考它就是釋放後使用（use-after-free）；就算僥倖沒事，ABA 模式（彈出 A、彈出 B、推回 A）也可能讓你的 CAS 以過時的 next 成功。因此正確的 Treiber 堆疊絕不只是那個赤裸的迴圈；它必須搭配一套回收方案——標籤指標、危害指標或 epoch——在實務上才安全。
void push(Node *n) { Node *old; do { old = head; n->next = old; } while (!CAS(&head, old, n)); } Node *pop(void) { Node *old, *next; do { old = head; if (!old) return NULL; next = old->next; /* 危險：old 此刻可能已被釋放 */ } while (!CAS(&head, old, next)); return old; /* 呼叫者必須安全地回收 old */ }
push 如所寫即安全；pop 才是在認真讀取 old->next 之前需要 ABA 防護與安全回收的部分。
赤裸的 Treiber 迴圈只在當作教學骨架時才正確；真實程式碼中 pop 路徑需要 ABA 防護與回收方案，否則它就是一個等著發生的釋放後使用。