Design Bounded Blocking Queue
Design Bounded Blocking Queue is a medium design data structures problem solved with the concurrency pattern.
The best approach, optimal (lock with two conditions), runs in O(1) per operation (excluding waiting) time and O(capacity) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (one monitor, wait and notifyall) up.
Problem
Design a thread-safe BoundedBlockingQueue that holds at most capacity integers and is used by several producer and consumer threads at the same time.
BoundedBlockingQueue(int capacity)creates an empty queue with the given maximum size.void enqueue(int element)addselementto the back. If the queue is full, the calling thread waits until a slot frees up.int dequeue()removes and returns the front element. If the queue is empty, the calling thread waits until an element arrives.int size()returns how many elements are in the queue right now.
Do not use a ready-made blocking queue from the standard library; build the waiting yourself from locks and conditions.
Examples
Example 1
- Input
capacity = 2; producer thread: enqueue(4), enqueue(9), enqueue(6); consumer thread (starts later): dequeue(), dequeue(); then size()- Output
dequeue returns 4, then 9; size() = 1- Why
- The producer blocks on enqueue(6) while the queue holds [4, 9]. The first dequeue frees a slot, so 6 goes in. Two items were removed, one is left.
Example 2
- Input
capacity = 1; consumer thread: dequeue(); producer thread (starts later): enqueue(5)- Output
dequeue returns 5- Why
- The consumer finds the queue empty and waits until the producer adds 5.
Constraints
1 <= capacity <= 300 <= element <= 201 <= number of producer threads, consumer threads <= 8- At most
40calls toenqueue,dequeueandsizein total.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (one monitor, wait and notifyAll) | O(1) per operation (excluding waiting) | O(capacity) |
| Optimal (lock with two conditions) | O(1) per operation (excluding waiting) | O(capacity) |
1Brute force (one monitor, wait and notifyAll)
O(1) per operation (excluding waiting)Adding to or removing from a linked deque is constant time.O(capacity)At most capacity elements are stored.Use the object's built-in monitor. Both operations synchronize on the queue object, wait in a loop while they cannot proceed, and wake every waiting thread after each change. It is correct but wakes producers and consumers alike, so many threads wake up only to go back to sleep.
- enqueue: while size == capacity, wait(); add the element; notifyAll().
- dequeue: while size == 0, wait(); remove the front; notifyAll(); return it.
- size: read the size while holding the same monitor.
class BoundedBlockingQueue {
private final int capacity;
private final Deque<Integer> q = new ArrayDeque<>();
public BoundedBlockingQueue(int capacity) {
this.capacity = capacity;
}
public synchronized void enqueue(int element) throws InterruptedException {
while (q.size() == capacity) wait();
q.addLast(element);
notifyAll();
}
public synchronized int dequeue() throws InterruptedException {
while (q.isEmpty()) wait();
int x = q.pollFirst();
notifyAll();
return x;
}
public synchronized int size() {
return q.size();
}
}import threading
from collections import deque
class BoundedBlockingQueue:
def __init__(self, capacity: int):
self.capacity = capacity
self.q = deque()
self.cond = threading.Condition()
def enqueue(self, element: int) -> None:
with self.cond:
while len(self.q) == self.capacity:
self.cond.wait()
self.q.append(element)
self.cond.notify_all()
def dequeue(self) -> int:
with self.cond:
while not self.q:
self.cond.wait()
x = self.q.popleft()
self.cond.notify_all()
return x
def size(self) -> int:
with self.cond:
return len(self.q)class BoundedBlockingQueue {
int capacity;
deque<int> q;
mutex m;
condition_variable cv;
public:
BoundedBlockingQueue(int capacity) : capacity(capacity) {}
void enqueue(int element) {
unique_lock<mutex> lock(m);
cv.wait(lock, [&] { return (int)q.size() < capacity; });
q.push_back(element);
cv.notify_all();
}
int dequeue() {
unique_lock<mutex> lock(m);
cv.wait(lock, [&] { return !q.empty(); });
int x = q.front();
q.pop_front();
cv.notify_all();
return x;
}
int size() {
lock_guard<mutex> lock(m);
return q.size();
}
};// JavaScript runs on one thread, so "blocking" means returning a Promise
// that resolves once the operation can complete. One shared wait list
// plays the role of a single monitor: every change wakes all waiters.
class BoundedBlockingQueue {
constructor(capacity) {
this.capacity = capacity;
this.q = [];
this.waiters = [];
}
wakeAll() {
const w = this.waiters;
this.waiters = [];
for (const resolve of w) resolve();
}
async enqueue(element) {
while (this.q.length === this.capacity) {
await new Promise((resolve) => this.waiters.push(resolve));
}
this.q.push(element);
this.wakeAll();
}
async dequeue() {
while (this.q.length === 0) {
await new Promise((resolve) => this.waiters.push(resolve));
}
const x = this.q.shift();
this.wakeAll();
return x;
}
size() {
return this.q.length;
}
}2Optimal (lock with two conditions)
O(1) per operation (excluding waiting)Each call does a constant amount of work under the lock and wakes at most one thread.O(capacity)At most capacity elements are stored.Use an explicit lock with two condition queues: producers wait on notFull, consumers wait on notEmpty. After an enqueue only one waiting consumer is signalled, and after a dequeue only one waiting producer. No thread is woken unless it may now be able to proceed.
- enqueue: lock; while full, await notFull; add the element; signal notEmpty; unlock.
- dequeue: lock; while empty, await notEmpty; remove the front; signal notFull; unlock; return it.
- size: lock, read the size, unlock.
class BoundedBlockingQueue {
private final int capacity;
private final Deque<Integer> q = new ArrayDeque<>();
private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
public BoundedBlockingQueue(int capacity) {
this.capacity = capacity;
}
public void enqueue(int element) throws InterruptedException {
lock.lock();
try {
while (q.size() == capacity) notFull.await();
q.addLast(element);
notEmpty.signal();
} finally {
lock.unlock();
}
}
public int dequeue() throws InterruptedException {
lock.lock();
try {
while (q.isEmpty()) notEmpty.await();
int x = q.pollFirst();
notFull.signal();
return x;
} finally {
lock.unlock();
}
}
public int size() {
lock.lock();
try {
return q.size();
} finally {
lock.unlock();
}
}
}import threading
from collections import deque
class BoundedBlockingQueue:
def __init__(self, capacity: int):
self.capacity = capacity
self.q = deque()
self.lock = threading.Lock()
self.not_full = threading.Condition(self.lock)
self.not_empty = threading.Condition(self.lock)
def enqueue(self, element: int) -> None:
with self.lock:
while len(self.q) == self.capacity:
self.not_full.wait()
self.q.append(element)
self.not_empty.notify()
def dequeue(self) -> int:
with self.lock:
while not self.q:
self.not_empty.wait()
x = self.q.popleft()
self.not_full.notify()
return x
def size(self) -> int:
with self.lock:
return len(self.q)class BoundedBlockingQueue {
int capacity;
deque<int> q;
mutex m;
condition_variable notFull, notEmpty;
public:
BoundedBlockingQueue(int capacity) : capacity(capacity) {}
void enqueue(int element) {
unique_lock<mutex> lock(m);
notFull.wait(lock, [&] { return (int)q.size() < capacity; });
q.push_back(element);
notEmpty.notify_one();
}
int dequeue() {
unique_lock<mutex> lock(m);
notEmpty.wait(lock, [&] { return !q.empty(); });
int x = q.front();
q.pop_front();
notFull.notify_one();
return x;
}
int size() {
lock_guard<mutex> lock(m);
return q.size();
}
};// JavaScript runs on one thread, so "blocking" means returning a Promise.
// Two separate wait lists act as the two conditions: an enqueue wakes
// one waiting consumer, a dequeue wakes one waiting producer.
class BoundedBlockingQueue {
constructor(capacity) {
this.capacity = capacity;
this.q = [];
this.notFull = [];
this.notEmpty = [];
}
async enqueue(element) {
while (this.q.length === this.capacity) {
await new Promise((resolve) => this.notFull.push(resolve));
}
this.q.push(element);
if (this.notEmpty.length > 0) this.notEmpty.shift()();
}
async dequeue() {
while (this.q.length === 0) {
await new Promise((resolve) => this.notEmpty.push(resolve));
}
const x = this.q.shift();
if (this.notFull.length > 0) this.notFull.shift()();
return x;
}
size() {
return this.q.length;
}
}Edge cases to test
- Capacity 1, so every enqueue after the first must wait for a dequeue
- Several producers blocked at once on a full queue
- Several consumers blocked at once on an empty queue
- Spurious wake-ups: a waiting thread must re-check its condition after waking
Hints
Hint 1
All three methods read or change shared state, so they need one lock guarding the queue.
Hint 2
A thread that cannot proceed must release the lock while it waits, otherwise nobody else can change the queue.
Hint 3
Always wait inside a while loop, not an if, and wake waiters after every change. Separate 'not full' and 'not empty' conditions avoid waking the wrong kind of thread.
FAQ
What is the best time complexity for Design Bounded Blocking Queue?
Optimal (lock with two conditions) runs in O(1) per operation (excluding waiting) time and O(capacity) extra space. Each call does a constant amount of work under the lock and wakes at most one thread.
Which pattern does Design Bounded Blocking Queue use?
It is a design data structures problem that uses the concurrency pattern.
Is there a brute force solution for Design Bounded Blocking Queue?
Yes. Brute force (one monitor, wait and notifyAll) takes O(1) per operation (excluding waiting) time and O(capacity) space. Use the object's built-in monitor.
Which edge cases should I test for Design Bounded Blocking Queue?
Capacity 1, so every enqueue after the first must wait for a dequeue; Several producers blocked at once on a full queue; Several consumers blocked at once on an empty queue; Spurious wake-ups: a waiting thread must re-check its condition after waking.