I got this question in a 2017 Wells white-board coding interview, and discussed with my friend Shanyou. We hoped to avoid locks and also avoid other synchronization devices such as atomic variables..
Q1: only a single producer thread and a single consumer thread and no other threads.
I put together a java implementation that can enqueue without synchronization, most of the time … See https://wp.me/p74oew-7mE
Q1b: Is it possible to avoid synchronization completely, i.e. single-threaded mode?
A: No. Consumer thread would have absolutely NO idea whatsoever how close it is to the producer end. No. We asneed a memory barrier at the very least.
Q2: what if there are multiple producer/consumer threads?
I believe we can use 2 separate locks for the two ends, rather than a global lock. This is more efficient but invites the tricky question “how to detect when the two ends meet“. I am not sure. I just hope the locks enforce a memory barrier.
Alternatively, we could use CAS on both ends, but see lockfree queue #popular IV