Изменения
→Корректная lock-free реализация
*/</font>
'''CAS'''(T, tail, tail.next.get())
== Проблема с <tex>pop</tex> ==
Если мы попытаемся воспользоваться написанной выше реализацией метода <tex>pop</tex>, инвариант очереди не будет соблюдён. В силу особенностей реализации метода <tex>push</tex>, в некоторые моменты <tex>T</tex> может указывать не на добавленный последним элемент, а на добавленный предпоследним. В таком случае, с помощью последовательности удалений можно добиться того, что <tex>H</tex> будет указывать на последний добавленный элемент, а <tex>T</tex> - на предпоследний. Таким образом, <tex>H</tex> будет указывать на вершину правее чем та, на которую указывает <tex>T</tex>, то есть инвариант очереди будет нарушен
== Корректная реализация <tex>pop</tex> ==
Основная проблема предыдущей реализации состоит в том, что в методе <tex>pop</tex> при перемещении <tex>H</tex>, мы никак не следили за положением <tex>T</tex>. Эту проблему можно исправить следующим образом: пусть в методе <tex>pop</tex> рабочий поток будет помогать переместить указатель <tex>T</tex> на последний добавленный элемент (аналогично действиям рабочего потока в методе <tex>push</tex>).
Для определения того, указывает ли <tex>T</tex> на последний добавленный элемент, воспользуемся следующим соображением: если <tex>T</tex> указывает на последний добавленный элемент, то <tex>T.get().next == '''null'''</tex>, так как за последним добавленным элементом нет других элементов. В противном случае <tex>T</tex> указывает на предпоследний добавленный элемент, и его надо передвинуть на последний добавленный.
'''def''' pop(): '''Int'''
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): <font color=green>//CAS-цикл</font>
head = H.get() <font color=green>//Сохраняем в локальные переменные текущие голову и хвост, а так же следующий за головным элемент</font>
tail = T.get()
nextHead = head.next.get()
'''if''' (head == tail):
<font color=green>/*
Если head и tail совпадают, это ещё не означает, что очередь пуста.
Возможно, что мы просто не успели подвинуть tail. Если tail.next не null,
то мы просто не успели подвинуть tail при добавлении.
*/</font>
'''if''' (nextHead == '''null'''):
<font color=green>// Следующего элемента нет, очередь пуста</font>
'''throw''' '''new''' EmptyException()
'''else''':
<font color=green>/*
push не успел подвинуть T, наш поток должен помочь
tail == head => tail.next == head.next
*/</font>
'''else''':
<font color=green>// Очередь гарантированно не пуста, следующий элемент существует</font>
result = nextHead.data
'''if''' ('''CAS'''(H, head, nextHead)):
<font color=green>/*
Если получилось переставить голову, то фиктивным элементом стал
H.next, результат - данные, которые в нём лежали. Если не получилось -
возвращаемся в начало метода и пробуем ещё раз
*/</font>
'''return''' result
==Примечания==
