Неблокирующие структуры данных в Java могут быть реализованы с использованием атомарных операций и циклов CAS (Compare-and-Swap). Вот пример минимальной реализации неблокирующего стека с методами push() и pop():
import java.util.concurrent.atomic.AtomicReference;
public class NonBlockingStack<T> {
private static class Node<T> {
final T value;
Node<T> next;
Node(T value) {
this.value = value;
}
}
private final AtomicReference<Node<T>> top = new AtomicReference<>();
public void push(T value) {
Node<T> newNode = new Node<>(value);
Node<T> oldTop;
do {
oldTop = top.get();
newNode.next = oldTop;
} while (!top.compareAndSet(oldTop, newNode));
}
public T pop() {
Node<T> oldTop;
Node<T> newTop;
do {
oldTop = top.get();
if (oldTop == null) {
return null; // Стек пуст }
newTop = oldTop.next;
} while (!top.compareAndSet(oldTop, newTop));
return oldTop.value;
}
}
В этой реализации используется класс AtomicReference, который обеспечивает атомарные операции чтения и записи ссылок. Каждый элемент стека представлен узлом Node, содержащим значение и ссылку на следующий узел.
Метод push() добавляет новый элемент на вершину стека. Он создает новый узел со значением и затем повторяет цикл CAS, чтобы попытаться обновить вершину стека на новый узел. Если операция CAS успешна, то новый узел успешно добавлен на вершину стека.
Метод pop() удаляет элемент с вершины стека. Он также использует цикл CAS для обновления вершины стека на следующий узел. Если операция CAS успешна, то возвращается значение удаленного узла.
Обратите внимание, что при использовании неблокирующих структур данных не гарантируется строгое соблюдение порядка операций между потоками. Это означает, что порядок, в котором элементы будут извлекаться из стека, может немного отличаться от порядка, в котором они были добавлены.
1606 вопрос-ответ по Java: https://github.com/DEBAGanov/interview_questions
Tелеграмм канал: https://t.me/DEBAGanov
Мое резюме: https://github.com/DEBAGanov