ConcurrentStack.java

ConcurrentStack.java

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Executors;

import java.util.concurrent.TimeUnit;

import java.util.concurrent.atomic.*;

/**

* ConcurrentStack

* <p/>

* Nonblocking stack using Treiber's algorithm

*/

//ThreadSafe

public class ConcurrentStack <E> {

AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();

public void push(E item) {

Node<E> newHead = new Node<E>(item);

Node<E> oldHead;

do {

oldHead = top.get();

newHead.next = oldHead;

} while (!top.compareAndSet(oldHead, newHead));

}

public E pop() {

Node<E> oldHead;

Node<E> newHead;

do {

oldHead = top.get();

if (oldHead == null)

return null;

newHead = oldHead.next;

} while (!top.compareAndSet(oldHead, newHead));

return oldHead.item;

}

private static class Node <E> {

public final E item;

public Node<E> next;

public Node(E item) {

this.item = item;

}

}

public static void main(String...args) {

int totalThreads = 10;

int totalIterations = 1000;

ExecutorService exc = Executors.newFixedThreadPool(totalThreads);

ConcurrentStack<String> cs = new ConcurrentStack<>();

for(int i = 0; i < totalIterations; i++) {

String tmp = "item" + i;

exc.submit(() -> cs.push(tmp));

exc.submit(() -> {

if(cs.pop()==null) {

System.out.println("stack empty.");

}

});

}

exc.shutdown();

try {

exc.awaitTermination(2, TimeUnit.SECONDS);

} catch (InterruptedException e) {

e.printStackTrace();

}

System.out.println(exc.isTerminated());

System.out.println(cs.pop());

}

}

The ConcurrentStack class implements a nonblocking, thread-safe stack using Treiber’s algorithm, a classic lock-free algorithm based on atomic operations. The stack's top is maintained as an AtomicReference to a singly linked list of Node<E> elements. Both push() and pop() methods use CAS (compare-and-set) loops to safely update the top pointer without locks, ensuring that concurrent modifications do not lead to inconsistent state. push() creates a new node, links it to the current head, and atomically updates the top; pop() reads the current head and attempts to CAS it to the next node. The main() method creates multiple threads using an executor to simulate concurrent push and pop operations. This implementation is highly efficient under high contention and demonstrates a scalable nonblocking data structure. However, due to the lack of fairness or coordination, threads may starve under extreme contention. This example showcases how atomic primitives enable building high-performance concurrent collections without relying on traditional synchronization mechanisms.