源码角度了解ConcurrentLinkedQueue

源码角度了解ConcurrentLinkedQueue

ConcurrentLinkedQueue是基于链表的线程安全的队列，队列遵循先进先出的策略，新元素插入到尾部，获取元素获取的是队列的头部元素，队列的元素不可以为null

一开始头部指针和尾部指针都指向null

入队列方法offer()方法

offer()方法是将元素插入队列尾部，因为队列是没有界限的，这个方法永远不会返回false

public boolean offer(E e) { checkNotNull(e); final Node<E> newNode = new Node<E>(e); for (Node<E> t = tail, p = t;;) { Node<E> q = p.next; if (q == null) { // p is last node if (p.casNext(null, newNode)) { if (p != t) // hop two nodes at a time casTail(t, newNode); // Failure is OK. return true; } } else if (p == q) p = (t != (t = tail)) ? t : head; else p = (p != t && t != (t = tail)) ? t : q; } }

根据传入的元素e创建新的节点

for循环，获取tail指针指向的节点，判断是否为尾结点，如果是尾结点，添加节点到尾部。一开始p和tail相等，q=p.next，q为null表示p指向的是尾结点，就可以添加新的节点到尾部了，调用casNext()方法让p的next指向新的节点，新节点的next是q

再添加节点的时候p同样指向了尾结点，p的下一个节点有指向新的节点，而tail指针指向的是倒数第二个元素，此时p指向倒数第二个节点，tail指向倒数第三个节点，p和tail不相等，调用casTail()更xin tail指向的节点为最新节点，也就是tail指向了最后一个节点。

入队两个节点后更新一次tail指针，失败也无所谓，然后返回true，只要保证p的下一个指针指向新节点就可以。

如果不是尾结点改变p的值，进一步for循环直到达到尾结点

出队列方法poll()方法

public E poll() { restartFromHead: for (;;) { for (Node<E> h = head, p = h, q;;) { E item = p.item; if (item != null && p.casItem(item, null)) { if (p != h) // hop two nodes at a time updateHead(h, ((q = p.next) != null) ? q : p); return item; } else if ((q = p.next) == null) { updateHead(h, p); return null; } else if (p == q) continue restartFromHead; else p = q; } } }

出队列和入队列的逻辑差不多

使用p指针指向头部节点，也就是说p=head q=p.next 此时p和q不相等，如果节点的值不为空，就可以出队列了，调用casItem()方便改变p的值，设置为null，此时p和head相等，并不更新head指针

当再有元素出队列的时候，p=head，head指向的元素已经是null，此时p.item为空，p移动到q指向的位置，再循环获取到的p.item不为空，设置为null，输出元素，此时p和head不相等，更新head指针指向的元素，head指针每出队列两个元素更新一次

空队列的判断

我们了解到，head指针和tail指针并不一定指向头结点和尾结点，我们怎么判断这个队列是不是空队列呢，我们看一下它的isEmpty()方法

public boolean isEmpty() { return first() == null; }

first()是从head指针指向的位置查找返回第一个不是null的元素，如果遍历完都是没有找到，返回null，此时isEmpty()方法就返回true了

总结

这篇文章讲了ConcurrentLinkedQueue的实现原理，它通过CAS来保证线程安全，head tail指针每两个元素的入队和出队才会更新一次，我们介绍了一下它的入队方法offer()和出队方法poll()的实现，已经如何判断队列为空

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话：

欢迎关注我❤️，点赞