Design a Thread-Safe Queue

Problem Design a queue data structure that multiple threads can use concurrently — producers enqueuing and consumers dequeuing — without race conditions, lost elements, or corrupted internal state.

Requirements

• enqueue(item) -> bool — add to the tail
• dequeue() -> Optional<T> — remove from the head
• size() -> int and isEmpty() -> bool
• Blocking variants: put(item) blocks while full, take() blocks while empty
• Safe under many concurrent producers and consumers; no element lost or returned twice

Core design

• Back the queue with a ring buffer (fixed capacity, head/tail indices) or a linked list (unbounded, node per element). Bounded is usually the right default — an unbounded queue turns a slow consumer into an out-of-memory crash instead of applying backpressure.
• Lock-based: guard head, tail, and size with a mutex. Hold it only for the pointer/index update — never across the caller's processing, or the queue serializes the whole pipeline. Blocking semantics come from condition variables: notFull and notEmpty, with consumers waiting on notEmpty and producers signalling it after an enqueue.
• Condition waits must sit in a while loop, not an if — spurious wakeups are real, and with multiple waiters another thread may consume the item between the signal and the wake.
• Lock-free: a ring buffer with atomic head/tail indices updated by compare-and-swap. Higher throughput under contention and no risk of a thread being descheduled while holding a lock, at the cost of far subtler correctness.
• Two-lock optimization: a linked queue can hold separate head and tail locks, letting one producer and one consumer proceed simultaneously since they touch opposite ends — only the empty-queue case makes them contend.
• size() is inherently approximate under concurrency: the value is stale the moment it returns. Callers must not branch on it (if (!isEmpty()) dequeue() is a race) — the API should make the check-then-act atomic instead.

Discussion points

• Blocking vs. non-blocking semantics: returning Optional.empty() on an empty queue pushes the retry decision to the caller and invites spin loops; blocking take() parks the thread but needs an interrupt/timeout path or shutdown deadlocks.
• Trade-off: mutex is simple and obviously correct but contended; lock-free scales but exposes the ABA problem and memory-reclamation hazards (freeing a node another thread still holds a pointer to).
• Memory ordering matters — publishing an element requires a release/acquire pair, or a consumer can see the index update before the element write lands.
• Edge cases: shutdown while consumers are blocked (poison pill vs. explicit close), and full-queue policy (block, drop-newest, drop-oldest, or throw).
• Fairness: neither a mutex nor a CAS loop guarantees FIFO among threads, so a producer can starve under load even though elements stay FIFO.
• Extension: a drainTo(collection) bulk operation amortizes lock acquisition across many elements, often a bigger win than going lock-free.