Java.Multithreading.Write a minimal non-blocking stack (only two methods – push() and pop()).

🔥 Let’s write a minimal non-blocking stack using lock-free programming with CAS (Compare-And-Swap) operations, leveraging AtomicReference.

⚙️ Requirements

• ✅ Non-blocking — no synchronized, no locks
• ✅ Two methods: push() and pop()
• ✅ Thread-safe using CAS logic

🧱 Tools: AtomicReference<Node>

We’ll use a linked list structure under the hood, and an AtomicReference as the pointer to the head of the stack.

✅ Minimal Lock-Free Stack Implementation

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeStack<T> {
    private static class Node<T> {
        final T value;
        final Node<T> next;

        Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }

    private final AtomicReference<Node<T>> head = new AtomicReference<>();

    public void push(T value) {
        Node<T> newNode;
        Node<T> currentHead;
        do {
            currentHead = head.get();
            newNode = new Node<>(value, currentHead);
        } while (!head.compareAndSet(currentHead, newNode));
    }

    public T pop() {
        Node<T> currentHead;
        Node<T> newHead;
        do {
            currentHead = head.get();
            if (currentHead == null) return null; // Stack is empty
            newHead = currentHead.next;
        } while (!head.compareAndSet(currentHead, newHead));
        return currentHead.value;
    }
}

💡 How It Works (CAS-Based)

• compareAndSet(expected, newValue) ensures atomic update:
  • If expected == current value, it sets the new one.
  • If not, another thread changed it → retry.

🧪 Example Usage

public class Main {
    public static void main(String[] args) {
        LockFreeStack<Integer> stack = new LockFreeStack<>();

        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop()); // 2
        System.out.println(stack.pop()); // 1
        System.out.println(stack.pop()); // null
    }
}

🧠 Notes

• ✅ This is lock-free, not wait-free
• 🚫 No support for size/traversal (not safe to add those in lock-free without more tricks)
• Great for high-performance systems where blocking is expensive