Design a thread-safe queue with a fixed capacity. Multiple producer and consumer threads share one BoundedBlockingQueue instance.

Implement these operations:

enqueue(element) inserts an element at the back of the queue. If the queue is full, it must block until space becomes available.
dequeue() removes and returns the element at the front. If the queue is empty, it must block until an element becomes available.
size() returns the current number of elements in the queue.

The queue must preserve first-in, first-out order, never contain more than capacity elements, and coordinate waiting threads without busy-waiting.

The judge creates the queue and starts producer and consumer threads. Your implementation should provide the synchronization inside the queue rather than create threads itself.

The judge also preloads the standard concurrency and collection APIs for each supported language. You do not need to add import, include, or using statements.

Example 1:

Input:

Output:

Explanation: Elements leave the queue in the same order in which they entered.

Example 2:

Input:

Output:

Constraints

1 <= capacity <= 1000
1 <= element <= 1_000_000
enqueue, dequeue, and size may be called concurrently.
The judge uses a finite, balanced collection of enqueue and dequeue operations.

Starter Code

Understanding the Problem

A mutex alone can protect the queue from simultaneous modification, but producers and consumers also need to wait for state changes:

Producers wait for the queue to become not full.
Consumers wait for the queue to become not empty.

These are different conditions over the same shared state, so one lock and two condition variables provide a direct design.

Waiting must always occur in a loop. A thread can wake because of a notification meant for another thread or because the condition changed again before it reacquired the lock.

Synchronization Strategy

Maintain:

A FIFO container.
The fixed capacity.
One mutex protecting both the container and its size.
A notFull condition for producers.
A notEmpty condition for consumers.

For enqueue:

Acquire the mutex.
Wait while the queue size equals the capacity.
Append the element.
Signal a waiting consumer.

For dequeue:

Acquire the mutex.
Wait while the queue is empty.
Remove the front element.
Signal a waiting producer.
Return the removed element.

size acquires the same mutex before reading the queue size.

Correctness

Every access to the FIFO container occurs while holding the same mutex, so enqueue, dequeue, and size operations cannot observe partially updated state.

An enqueue proceeds only when the queue contains fewer than capacity elements. Therefore, the capacity is never exceeded. A dequeue proceeds only when the queue is non-empty, so it never removes a nonexistent element.

Enqueue adds only at the back and dequeue removes only from the front. Because these modifications are serialized by the mutex, elements leave in FIFO order.

After enqueue adds an element, it wakes a consumer that may be waiting for a non-empty queue. After dequeue frees a slot, it wakes a producer that may be waiting for space. Thus, blocked operations resume when their required state transition occurs.

Code

Complexity Analysis

Using a deque or queue with constant-time front removal:

enqueue: O(1) time.
dequeue: O(1) time.
size: O(1) time.
Space complexity: O(capacity) for stored elements and O(1) synchronization state.

Design Bounded Blocking Queue