# ConcurrentLinkedQueue

# ConcurrentLinkedQueue

入队将节点放入队尾，出队将节点从队首移除

特性：

  1. 入队后不一定会修改tail指针
  2. 出队不一定会更新head指针

# 节点

# 入队

  1. 将入队节点设置到当前队尾节点的 next 节点上；
  2. 更新tail节点，
    1. 如果tail节点的next节点不为空，则将入队节点设置为 tail节点，
    2. 如果tail节点的next节点为空，则将入队节点设为tail节点的next节点。
public boolean offer(E e) {
    ...
    final Node<E> newNode = new Node<E>(e);

    for (Node<E> t = tail, p = t;;) {
        Node<E> q = p.next;
        if (q == null) {
            if (p.casNext(null, newNode)) {
                if (p != t) 
                    casTail(t, newNode);
                return true;
            }
        }
        else if (p == q)
            p = (t != (t = tail)) ? t : head;
        else
            p = (p != t && t != (t = tail)) ? t : q;
    }
}

# 出队

head节点的元素

  1. 不为null，则弹出head中的元素，并设置head的元素为null，head指针不变
  2. 为null，更新head节点
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;
        }
    }
}
  1. h节点在内循环中每次不会改变，而跳出内循环后再次进入h节点可能会变
  2. h节点是临时的head节点
  3. 每次从p节点cas成功更新元素后，要检查节点是否是h，不是则更新h为p的next或者p本身。
  4. h节点的元素为空，或CAS更改为空的时候失败，则看next节点，next节点为空，则队列为空，更改h节点，并返回null
  5. 第三分支：p=p.next，应该是p和p.next指针都被出队了，表明外部head已经变更，重新开始循环
  6. 第四分支：不是初始化，p指针前进一次
ConcurrentLinkedQueue