美文网首页
ConcurrentLinkedQueue的入队和出队操作

ConcurrentLinkedQueue的入队和出队操作

作者: 上海马超23 | 来源:发表于2017-05-23 10:33 被阅读0次

ConcurrentLinkedQueue有两个指针属性:head和tail,方便快速定位到当前线程认为的头节点和尾节点。

ConcurrentLinkedQueue的特性允许tail指针指向的不是最新的尾节点(高并发操作下要保证tail指针的同步,会影响性能吧?)

因为tail指针不能保证正确的同步,所以判断尾节点的方式是 node.next == null

出队poll操作

一般情况下,找到头一个非null的节点p,将节点p的内容获取后置null。

从源代码可以看出,更新head到p的下一个节点,不是每次都会做的。当头节点p的内容不是null,出队后,p的内容变成null,但head还是指向p的;只有当下一次出队,p已经是null的前提下,才会将p.next出队并置null,然后将head指向p.next的next。

满足上述head指针需要更新的条件下,将head指向出队节点p的下一个节点。此时,原来的头节点p的next是指向p本身,成为哨兵节点。(理论上,ConcurrentLinkedQueue的删除节点操作,都会把该节点设置成哨兵节点吧?)

updateHead 更新头节点的方法

1.先判断原来的头节点和要更新成头节点的节点是不是同一个

2.head指针指向新的节点

3.原来头节点没用了,next指向本身,变成哨兵节点

在高并发的场景下,在迭代节点过程中可能会指向哨兵节点,ConcurrentLikedQueue的策略就是重新从head指针开始迭代。

入队offer操作

casTail更新tail指针,比更新head指针的逻辑简单多了。更新head指针除了要移动head指针外,还需要将原head节点失效,设置成哨兵节点,而tail指针不需要后面一步。

在迭代寻找尾节点的时候,查到哨兵节点的时候,会先判断tail指针是不是已经被别的线程更新过了,如果更新过就从该tail开始迭代,很有可能该tail指针是正确指向尾节点的。如果没有被更新过,就从head的位置开始迭代。

相关文章

  • ConcurrentLinkedQueue的入队和出队操作

    ConcurrentLinkedQueue有两个指针属性:head和tail,方便快速定位到当前线程认为的头节点和...

  • 数组实现队列之循环队列

    对于链表实现方式,队列的入队、出队操作和栈是大同小异的。但对于数组实现方式来说,因为数组的长度固定,队列的入队和出...

  • ConcurrentLinkedQueue

    ConcurrentLinkedQueue 是利用依赖CAS实现的基于链接节点的无界安全队列。 入队 出队列

  • 蓝杯二十二

    /*队列操作问题描述?队列操作题。根据输入的操作命令,操作队列(1)入队、(2)出队并输出、(3)计算队中元素个数...

  • 第五讲-队列

    队列:先进先出 基本操作:出队(enqueue)or入队(dequeue) 顺序队列和链式队列 用数组实现的队列叫...

  • 蓝桥杯 算法提高 队列操作 c++

    问题描述队列操作题。根据输入的操作命令,操作队列(1)入队、(2)出队并输出、(3)计算队中元素个数并输出。输入格...

  • 13. ConcurrentLinkedQueue/Deque

    AQS内部的阻塞队列实现原理:基于双向链表,通过对head/tail进行CAS操作,实现入队和出队。 Concur...

  • 京东JAVA笔试两题

    通过队列实现 queue.size获得对应的总数大小 进行相应的入队出队操作

  • 数据结构-堆和优先队列

    优先队列 普通队列: 先进先出; 后进后出优先队列: 出队顺序和入队顺序无关; 和优先级有关 优先队列可以让操作系...

  • 队列

    循环队列 顺序存储 存储类型 初始化 判队空 入队 出队 链式存储 存储结构 初始化 判队空 入队 出队

网友评论

      本文标题:ConcurrentLinkedQueue的入队和出队操作

      本文链接:https://www.haomeiwen.com/subject/dnywxxtx.html