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.

• 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.

• 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).

• 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).

• 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.