Problem
Implement a thread-safe bounded blocking queue that has the following methods:
BoundedBlockingQueue(int capacity)
The constructor initializes the queue with a maximumcapacity
.void enqueue(int element)
Adds anelement
to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full.int dequeue()
Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty.int size()
Returns the number of elements currently in the queue.
Your implementation will be tested using multiple threads at the same time.
Each thread will either be a producer thread that only makes calls to the
enqueue
method or a consumer thread that only makes calls to the dequeue
method. The size
method will be called after every test case.
Please do not use built-in implementations of bounded blocking queue as this will not be accepted in an interview.
Examples
Example 1:
|
|
Example 2:
|
|
Constraints:
1 <= Number of Prdoucers <= 8
1 <= Number of Consumers <= 8
1 <= size <= 30
0 <= element <= 20
- The number of calls to
enqueue
is greater than or equal to the number of calls todequeue
. - At most
40
calls will be made toenque
,deque
, andsize
.
Solution
Method 1 – Condition Variables and Locks (Producer-Consumer Pattern)
Intuition
To implement a thread-safe bounded blocking queue, we use a queue to store elements, a lock to synchronize access, and two condition variables: one to wait for space (not full) and one to wait for items (not empty). Producers block when the queue is full, and consumers block when the queue is empty.
Approach
- Use a queue (e.g., deque) to store elements.
- Use a lock to synchronize access to the queue.
- Use two condition variables:
not_full
andnot_empty
. - In
enqueue
, acquire the lock, wait onnot_full
if the queue is full, add the element, notifynot_empty
, and release the lock. - In
dequeue
, acquire the lock, wait onnot_empty
if the queue is empty, remove and return the element, notifynot_full
, and release the lock. - In
size
, acquire the lock, return the current size, and release the lock.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(1)
for enqueue, dequeue, and size, as all operations are on a queue. - 🧺 Space complexity:
O(capacity)
, for storing up tocapacity
elements in the queue.