Implement a lock-free stack using atomic CAS operations and explain the ABA problem.

A lock-free data structure uses compare-and-swap (CAS) instead of mutexes — concurrent access without blocking. This is an advanced topic demonstrating deep understanding of memory ordering and Go's atomic package.

// Lock-free stack using atomic.Pointer (Go 1.19+)
type node[T any] struct {
    val  T
    next *node[T]
}

type LockFreeStack[T any] struct {
    head atomic.Pointer[node[T]]
}

func (s *LockFreeStack[T]) Push(val T) {
    n := &node[T]{val: val}
    for {
        old := s.head.Load()       // atomic read of current head
        n.next = old               // link new node to current head
        if s.head.CompareAndSwap(old, n) {
            return // success: head changed from old to n atomically
        }
        // CAS failed: another goroutine modified head; retry
    }
}

func (s *LockFreeStack[T]) Pop() (T, bool) {
    for {
        old := s.head.Load()
        if old == nil { var z T; return z, false }
        if s.head.CompareAndSwap(old, old.next) {
            return old.val, true
        }
    }
}

// ABA PROBLEM:
// Goroutine 1 reads head = A; pauses
// Goroutine 2: pops A, pushes B, pops B, pushes A again (same pointer!)
// Goroutine 1 resumes: CAS sees head == A → "unchanged" → succeeds
// But B has been removed — the stack is now corrupted

// WHY GO'S GC PREVENTS THE ABA PROBLEM:
// The GC does not reuse memory from a node until ALL pointers to it are gone
// If Goroutine 1 holds a reference to node A, A's memory is not recycled
// So when CAS sees the same pointer, it is guaranteed to be the same object
// → ABA is largely eliminated in GC-managed languages

Invest now in Acorns!!! 🚀
Join Acorns and get your $5 bonus!

Acorns is a micro-investing app that automatically invests your "spare change" from daily purchases into diversified, expert-built portfolios of ETFs. It is designed for beginners, allowing you to start investing with as little as $5. The service automates saving and investing. Disclosure: I may receive a referral bonus.

Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.

Webull! Receive free stock by signing up using the link: Webull signup.