Изменения
Нет описания правки
Очередь моделируется с помощью односвязного списка. Каждый элемент списка (<tex>Node</tex>) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).
'''case class''' Node<'''T'''>('''val''' data: '''T''', '''val''' next: AtomicReference<Node<'''T'''>>)
Если узел <tex>node</tex> является последним в списке, то его <tex>next</tex> указывает на <tex>null</tex>.
Узел списка, на который указывает <tex>H</tex>, является фиктивным (''dummy''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.
'''class''' Queue<'''T'''> dummy = new Node<'''T'''>(null, new AtomicReference<Node>(null)) head = new AtomicReference<Node<'''T'''>>(dummy) tail = new AtomicReference<Node<'''T'''>>(dummy)
// TODO; картинка
Будем поддерживать следующий инвариант: в нашей очереди <tex>H</tex> указывает на узел, находящийся не правее узла, на который указывает <tex>T</tex>
==Идея реализации==
=== Удаление элемента ===
Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.
'''def''' pop(): '''T'''
if (H.next == null):
'''throw''' new EmptyException()
H = H.next
return H.data <font color=green>H - новый фиктивный элемент</font>
=== Добавление элемента ===
==Примечания==
