Изменения
Нет описания правки
T.next = newTail <font color=green>//Добавление новой вершины в очередь</font>
T = T.next <font color=green>//Изменение хвоста списка</font>
== Многопоточная реализация ==
Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>)
=== Удаление элемента ===
Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.
'''def''' pop(): '''Int'''
while (true): <font color=green>//Поток пытается в CAS - цикле поменять указатель на H, пока не получится</font>
head = H.get()
if (head.next == null):
'''throw''' new EmptyException()
newHead = head.next.get()
if (CAS(H, head, nextHead)):
return newHead.data
=== Добавление элемента ===
Создадим новый узел списка, и добавим его в конец очереди.
'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
while (true): <font color=green>//Поток пытается в CAS - цикле поменять T.next, пока не получится</font>
tail = T.get()
curTail = tail.next
if (CAS(curTail, null, newTail)): <font color=green>//Поток пытается добавить элемент в конец очереди</font>
break
while (true): <font color=green>//Поток пытается в CAS - цикле поменять указатель на T, пока не получится</font>
tail = T.get()
nextTail = tail.next.get()
if (CAS(T, tail, nextTail)):
break
При этом мы сталкиваемся со следующей проблемой
=== Описание проблемы ===
==Примечания==
