TRT
Sign in
mediumExpertLeetCode#mutex#condition variable#bounded buffer

Design a bounded blocking queue

Build a thread-safe queue with a fixed capacity: enqueue blocks when full, dequeue blocks when empty, and no call busy-waits.

The Runtime Theory Team1 min read
Taught inData races and locksPro — members onlyTwo threads incrementing one counter can both be correct line by line and still lose updates. This lesson defines a data race, shows what a mutex fixes, and prices the lock: fast path, futex slow path, contention, convoying and spinlocks.
Solve it

Solving happens on the judge — come back and mark it done

Sample cases

incapacity = 3; enqueue(5), enqueue(6), dequeue(), size()

outdequeue returns 5, size() returns 1

incapacity = 1; enqueue(7); second thread enqueue(8) blocks; dequeue()

outsecond thread waits, then returns 7, size() is 1

incapacity = 2; first thread dequeue() on empty; enqueue(9)

outfirst thread waits, then returns 9, size() is 0

incapacity = 3; enqueue(10), enqueue(11), enqueue(12), dequeue(), dequeue(), size()

out10, 11, size() is 1

Implement a bounded blocking queue: BoundedBlockingQueue(capacity) with enqueue(element), dequeue() and size(). enqueue blocks while the queue is full, dequeue blocks while it is empty, and neither call may busy-wait. size() returns the count without blocking.

The judge drives the calls from several threads at once, so the cases that decide your score are the ones where a thread reaches the queue at the wrong moment: one that arrives full, one that arrives empty, and two that wake at the same time.

Before you code

Settle what protects the queue and what wakes the waiters. One mutex guards the buffer, the count and both waiting sets. The blocking calls wait on a condition variable while holding that lock, and the operation that frees a slot or adds an element wakes one waiter of the right kind. The order of check and wait is the design: re-check the condition in a loop on every wake-up, never once, because a notification can land between the check and the sleep, and because a wake-up without a state change is legal.

Hints

  1. A fixed-capacity ring buffer with a head index and a count answers full and empty with one comparison each, and never moves the data.
  2. Full and empty are two conditions. Either keep two condition variables, one per waiting set, or one variable plus a loop that re-checks the condition you actually care about after every wake-up.
  3. Notify only after the state change, with the lock still held or immediately after releasing it. Wake a waiter before mutating and it can return to sleep on the old state.
  4. Dequeue mirrors enqueue: wait while the count is zero, take the element at head, advance head modulo capacity, decrement the count, then notify.

What it practices

Mutexes, condition variables and the wait-notify discipline, from Data races and locks.

More practice in this track

hard · dsaDesign a skip listeasy · dsaRange sum query: immutableeasy · dsaRunning sum of an array

Not started

Sign in to save your learning progress.

Sign in to save