Getting Ready: Blocking Queue

Almost every concurrent system you've ever used depends on a blocking queue somewhere in its internals. When a web server like Tomcat accepts incoming HTTP requests, it drops them into a bounded queue; a pool of worker threads picks them up one by one. When a logging framework like Logback writes entries asynchronously, it pushes log records into a blocking queue so the application thread doesn't stall on disk I/O. When a message broker like RabbitMQ routes messages between producers and consumers, every internal channel is backed by a bounded, thread-safe buffer.

The blocking queue is the canonical implementation of the Producer-Consumer pattern (Fundamentals S15). Producers add items to the queue, consumers remove them, and the queue itself handles all the difficult coordination: making producers wait when the buffer is full, waking consumers when data arrives, and ensuring no item is lost or duplicated even when dozens of threads operate simultaneously.

Java ships java.util.concurrent.ArrayBlockingQueue and LinkedBlockingQueue as first-class concurrency utilities. Python provides queue.Queue in its standard library. These are not convenience wrappers — they are battle-tested synchronization primitives that every professional developer relies on. Understanding how they work internally, from the lock that guards the buffer to the condition variables that coordinate blocking and waking, is what separates someone who merely uses concurrency from someone who truly understands it.

Interviewers ask this problem because it's the most concentrated test of concurrency fundamentals: you need a mutex to protect shared state, two condition variables to implement blocking in both directions, a circular buffer for O(1) operations, and careful signal/wait logic to avoid deadlocks and lost wake-ups. It's compact enough to fit a 45-minute interview but deep enough to reveal whether you genuinely understand thread synchronization.

By the end of this design problem, you will be able to:

• Design a bounded, thread-safe queue using a circular array as the internal buffer, a mutex to protect shared state, and two condition variables to coordinate blocking between producers and consumers
• Understand the Producer-Consumer pattern at the implementation level — not just the concept, but the exact lock/wait/signal mechanics that make it work (Fundamentals S15)
• Implement the design in Python using threading.Lock and threading.Condition, with a clear explanation of why Python's GIL does not eliminate the need for explicit synchronization
• Implement the design in Java using ReentrantLock and Condition objects from java.util.concurrent.locks, the idiomatic Java approach for fine-grained concurrency control
• Identify and prevent concurrency bugs — race conditions on the size counter, lost wake-ups from incorrect signaling, and spurious wake-ups that require while-loop guards
• Test concurrent code using multi-threaded stress tests that verify thread safety, FIFO ordering, and correct blocking behavior
• Build a UML class diagram that models the queue's interface, implementation, and its relationship to synchronization primitives

Before starting this problem, make sure you're comfortable with:

• Concurrency Concepts — threads, mutexes, critical sections, and the concept of shared mutable state causing race conditions (Fundamentals S14). You must understand why unsynchronized access to shared data is dangerous before you can appreciate the solution.
• Concurrency Patterns — specifically the Producer-Consumer pattern and how condition variables coordinate blocking and waking between threads (Fundamentals S15). The blocking queue IS the Producer-Consumer pattern made concrete.
• OOP Interfaces and Abstract Classes — we'll define a BlockingQueue interface and an ArrayBlockingQueue implementation (Fundamentals S4)
• UML Class Diagrams — how to read class boxes, interface stereotypes, and dependency relationships (Fundamentals S5)
• Basic Data Structures — understanding how a circular array (ring buffer) works: head/tail pointers that wrap around using modulo arithmetic

This is one of four Concurrency difficulty problems (DP33-DP36). If you haven't studied Fundamentals S14 and S15, complete those first — this problem assumes you already know what a mutex is and why race conditions happen. We focus on applying those concepts to build a real synchronization primitive.

We will design: A bounded, thread-safe blocking queue that supports put(item) (blocks when full), take() (blocks when empty), and basic inspection methods (size(), is_empty(), is_full()). The internal buffer is a fixed-size circular array. Synchronization uses a single lock with two condition variables.

We will NOT design: Unbounded queues, priority queues, delay queues, transfer queues, or any of the other specialized queue types in java.util.concurrent. We also will not design distributed queues (Kafka, SQS), persistent queues, or message serialization. This is a Low Level Design exercise focused on the in-memory synchronization mechanics.

Why separate Python and Java tutorials:

Unlike most design problems where both languages appear in a single code tutorial, this concurrency problem has dedicated Python and Java implementation tutorials. The reason is fundamental: Python's threading.Condition wraps a lock and provides wait()/notify() with different semantics than Java's ReentrantLock and Condition.await()/signal(). Python's GIL adds a layer of nuance that doesn't exist in Java. The locking APIs, exception handling patterns, and idiomatic concurrency styles differ enough that doing justice to both languages requires separate, focused tutorials.

What makes this problem unique among concurrency problems:

• Unlike the Thread Pool (DP34), which is a higher-level coordinator, the blocking queue is a raw synchronization primitive — the lowest level of concurrency infrastructure
• Unlike the Rate Limiter (DP35), which manages time-based constraints, the blocking queue manages space-based constraints (bounded capacity)
• Unlike the Concurrent HashMap (DP36), which uses segment locking or CAS for fine-grained access, the blocking queue uses a single lock with condition variables for coordinated blocking