A lock-free FIFO queue
A FIFO (first in, first out) queue is a data structure where the elements are popped out in the same order in which they were inserted. This is in contrast to a stack, where the order is LIFO (last in, first out). In case you need to refresh your memory of these terms, head to https://www.geeksforgeeks.org/queue-data-structure/.
One obvious way for making a queue safer is to use a single lock to make it thread-safe. We could use either an explicit lock (a ReentrantLock) or an intrinsic lock by just making the methods synchronized.
This will, of course, work; however, it will hurt concurrency. At any point, only one thread will be able to push or pop the queue.
Our goal is to increase the concurrency while at the same time ensuring thread safety. Could we allow two threads, one producing elements to the queue and another consuming elements from it?
The following class shows a thread-safe and bounded FIFO queue using two locks. One lock is used to protect the insertion...
