Design Bounded Blocking Queue
Medium · Design · Design · Queue · Concurrency
Problem
Build a bounded blocking queue: a first-in, first-out queue that holds at most capacity elements, where a producer that finds it full waits for room and a consumer that finds it empty waits for an element.
- BoundedBlockingQueue(capacity) — create an empty queue
- enqueue(element) — a producer adds element at the back
- dequeue() — a consumer removes and receives the element at the front
- size() — how many elements are in the queue right now
How this practice version differs from the original. LeetCode runs your class on real threads, and enqueue / dequeue really block. The in-browser Python cannot start threads, so here the grader plays the thread scheduler: each call in a test is one thread arriving, in that order, and a call that would block parks instead of hanging. Your class does the bookkeeping that the lock and condition variables would do in the threaded version — who is waiting, and who is released, in which order:
- dequeue() returns the front element, or -1 if the queue is empty; that consumer is now waiting.
- enqueue(element): if consumers are waiting, the longest-waiting one receives element right away and enqueue returns element (the value that consumer finally gets). Otherwise it returns -1: the element joins the queue, or, if the queue is full, the producer waits holding it.
- When a dequeue frees a slot and producers are waiting, the longest-waiting producer's element enters the queue at once.
- size() counts elements in the queue only, not ones held by waiting producers.
Reading the non--1 results of dequeue and enqueue in order, then the final size(), gives LeetCode's expected output. Elements are between 0 and 20, so -1 never collides with one.
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and each call reports its return value.
Examples
Input: BoundedBlockingQueue(2), enqueue(1), dequeue(), dequeue(), enqueue(0), enqueue(2), enqueue(3), enqueue(4), dequeue(), size() Output: -1, 1, -1, 0, -1, -1, -1, 2, then 2
The second dequeue finds the queue empty and waits; enqueue(0) hands 0 straight to it. enqueue(4) finds [2,3] full and waits; the next dequeue returns 2 and lets 4 in, leaving [3,4].
Input: BoundedBlockingQueue(3), enqueue(1), enqueue(0), enqueue(2), dequeue(), dequeue(), dequeue(), enqueue(3), size() Output: -1, -1, -1, 1, 0, 2, -1, then 1
LeetCode accepts any order of 1, 0, 2 here because its three consumers race. With the calls taken in order, first in is first out.
Constraints
- 1 <= capacity <= 30 (stress tests go to 1,000)
- 0 <= element <= 20
- LeetCode: 1 to 8 producer threads and 1 to 8 consumer threads, at most 40 calls
- Stress tests replay up to 2,000 calls
- Do not use a built-in blocking queue (queue.Queue, ArrayBlockingQueue)
Approaches
- One list for queued and parked elements — time O(capacity + parked) per dequeue, space O(capacity + parked producers)
Follow-up
Write the real threaded version: one lock with two conditions (not full, not empty), or two semaphores counting free slots and available items. Why must the wait sit in a while loop rather than an if, and what goes wrong if both sides share one condition and you call notify instead of notify_all?
Related problems
Start free on Cariara · Coding problems · System design studio
