I'm single.

You may already be familiar with the lock-free MPSC (multi-producer, single-consumer) queue shown on our homepage. This problem tests whether you understand how to generalize those ideas to SPSC concurrency.

Implement the class SPSCQueue, which is a lock-free single-producer single-consumer queue.

Constructor

SPSCQueue(capacity)

• capacity specifies the maximum amount of elements that may exist in the queue at any time.

• capacity must be a power of 2 and greater than 2. Throw an exception if it isn't.

Methods

push(element)

• Attempts to enqueue element.

• Returns true if the enqueue succeeds.

• Returns false if the queue is full at the operation's linearization point (no spurious failures).

pop(out)

• Attempts to dequeue an element and store it in out.

• Returns true if the dequeue succeeds.

• Returns false if the queue is empty at the operation’s linearization point (no spurious failures).

Notes

• Exactly one producer thread and exactly one consumer thread may call push/pop concurrently.

• The implementation must be lock-free (no std::mutex, no condition variables, etc.). Using a lock may result in a compilation error.

• The grader uses stress tests to detect corruption (duplicates/missing) and deadlocks, but does not formally verify linearizability.

• Type constraints (standard version):

  • You may assume the stored type T is default-constructible.

• You may assume the queue will not be destroyed during concurrent push or pop operations.

• You do not need to write any input/output parsing.

• A queue constructed with capacity = N must allow N successful push calls before reporting full.

• Because there are only two threads, there is very little opportunity for data corruption, allowing incorrect solutions to pass the judge. Therefore, this problem has been marked as unrated.