源码角度了解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()的实现,已经如何判断队列为空
❤️ 感谢大家
如果你觉得这篇内容对你挺有有帮助的话:
- 欢迎关注我❤️,点赞👍🏻,评论🤤,转发🙏
- 关注
盼盼小课堂
,定期为你推送好文,还有群聊不定期抽奖活动,可以畅所欲言,与大神们一起交流,一起学习。 - 有不当之处欢迎批评指正。