Prerequisite: Based on x86 architecture, Linux environment

Core idea: realize based on linked list

First declare the linked list

* public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; *}}Copy the code

Enqueue

Team entry operation is divided into three steps:

  1. Creating a New node
  2. Point the next pointer of the current tail node to the new node
  3. Modify the tail pointer to the newly created node

See the poll method of ConcurrentLinkedQueue

public E poll() { restartFromHead: for (;;) { for (Node<E> h = head, p = h, q;; p = q) { final E item; if ((item = p.item) ! = null && p.casItem(item, null)) { // Successful CAS is the linearization point // for item to be removed from this queue. 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; }}}Copy the code

`}

Dequeue

Getting out of the queue is much easier than getting in. Just move the head back and pull out the data

Okay, I admit I don’t understand this part, but I have to get the general idea, just for the interview, just look around

Reference Papers:

  • “Implementing Lock-Free Queues”, a paper presented by John D. Valois at the International Congress on Parallel and Distributed Systems systems, Las Vegas, October 1994
  • Maged M. Michael and Michael L. Scott of The University of Rochester, New York, USA, published a paper “Simple, Fast, And Practical non-blocking and Blocking ConcurrentQueue Algorithms