Problem 41.3 · Concurrency-Aware Data StructuresMedium

Design Bounded Blocking Queue

What it teaches: A lock with two conditions: producers wait on "not full", consumers on "not empty".

Practise it on judges as “Design Bounded Blocking Queue”.

In plain words

Picture a conveyor belt with room for only a few boxes. Packers put boxes on, shippers take them off. If the belt is full, a packer has to wait; if it's empty, a shipper has to wait. Only one person may touch the belt at a time, and whoever changes it rings a bell so the waiting people check again.

Return the removed element from dequeue and the count from size. Example: capacity 2: enqueue(1), enqueue(0), dequeue(), size() → 1, 1.

The problem

Design BoundedBlockingQueue(capacity) with enqueue(element) (blocks while full), dequeue() (blocks while empty) and size(), safe for many producer and consumer threads. The tests call it from one thread without triggering blocking.

Example 1

Input: cap 2: enqueue(1), enqueue(0), dequeue(), size()
Output: 1, 1

Constraints

1 ≤ capacity ≤ 30

Pattern clues in the wording

→ Producer-consumer
→ Wait while full / empty

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

BoundedBlockingQueue · starter

import java.util.*;
import java.util.concurrent.locks.*;

class BoundedBlockingQueue {
    public BoundedBlockingQueue(int capacity) {}
    public void enqueue(int element) throws InterruptedException {}
    public int dequeue() throws InterruptedException { return 0; }
    public int size() { return 0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["BoundedBlockingQueue","enqueue","enqueue","dequeue","size","enqueue","size","dequeue","dequeue","size"] args = [[2],[1],[0],[],[],[5],[],[],[],[]]	[null,null,null,1,1,null,2,0,5,0]

From slow to fast

Approaches

1. Lock + two conditions · O(1) per operation 2. synchronized + wait/notifyAll · O(1) per operation (more wake-ups)

Lock + two conditions

Time O(1) per operation Space O(capacity)

enqueue: while full, notFull.await(); add; notEmpty.signal(). dequeue: while empty, notEmpty.await(); remove; notFull.signal().

Approach 1

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

class BoundedBlockingQueue {
    private final Deque<Integer> items = new ArrayDeque<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition(), notEmpty = lock.newCondition();

    public BoundedBlockingQueue(int capacity) { this.capacity = capacity; }

    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try {
            while (items.size() == capacity) notFull.await();
            items.addLast(element);
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    public int dequeue() throws InterruptedException {
        lock.lock();
        try {
            while (items.isEmpty()) notEmpty.await();
            int x = items.removeFirst();
            notFull.signal();
            return x;
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        lock.lock();
        try { return items.size(); } finally { lock.unlock(); }
    }
}

Verdict: Separate conditions wake only the right kind of waiter.

synchronized + wait/notifyAll

Time O(1) per operation (more wake-ups) Space O(capacity)

One monitor; notifyAll after every change so both producers and consumers re-check.

▶ Dry run: synchronized methods + wait/notifyAllcapacity 2: enqueue(1), enqueue(0), dequeue(), size()

queue (front first)(queue)

state(vars)

size: 1 of 2

Step 1/4enqueue(1): take the lock. The queue is not full, so the while loop doesn't wait. Add 1 at the back and notifyAll.

Approach 2

import java.util.ArrayDeque;
import java.util.Deque;

class BoundedBlockingQueue {
    private final Deque<Integer> items = new ArrayDeque<>();
    private final int capacity;

    public BoundedBlockingQueue(int capacity) { this.capacity = capacity; }

    public synchronized void enqueue(int element) throws InterruptedException {
        while (items.size() == capacity) wait();
        items.addLast(element);
        notifyAll();
    }

    public synchronized int dequeue() throws InterruptedException {
        while (items.isEmpty()) wait();
        int x = items.removeFirst();
        notifyAll();
        return x;
    }

    public synchronized int size() { return items.size(); }
}

Verdict: Simpler, slightly less efficient.

Before you submit

Edge cases and common mistakes

Test these inputs

Capacity 1
Many producers, one consumer

Mistakes people make

Unlocking outside finally (an exception would leave the lock held forever).
if instead of while around await().

Interview

Follow-up questions

Why not just use ArrayBlockingQueue?

Connect the dots

Where this shows up in real systems

System Design · Topic 5.8 — Producer / ConsumerThe blocking queue that producer-consumer systems are built on.

Command Palette