Skip to content

1188. Design Bounded Blocking Queue 👍

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// LeetCode doesn't support C++20 yet, so we don't have std::counting_semaphore
// or binary_semaphore.
#include <semaphore.h>

class BoundedBlockingQueue {
 public:
  BoundedBlockingQueue(int capacity) {
    sem_init(&enqueueSemaphore, /*pshared=*/0, /*value=*/capacity);
    sem_init(&dequeueSemaphore, /*pshared=*/0, /*value=*/0);
  }

  ~BoundedBlockingQueue() {
    sem_destroy(&enqueueSemaphore);
    sem_destroy(&dequeueSemaphore);
  }

  void enqueue(int element) {
    sem_wait(&enqueueSemaphore);
    q.push(element);
    sem_post(&dequeueSemaphore);
  }

  int dequeue() {
    sem_wait(&dequeueSemaphore);
    const int element = q.front();
    q.pop();
    sem_post(&enqueueSemaphore);
    return element;
  }

  int size() {
    return q.size();
  }

 private:
  queue<int> q;
  sem_t enqueueSemaphore;
  sem_t dequeueSemaphore;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class BoundedBlockingQueue {
  public BoundedBlockingQueue(int capacity) {
    this.enqueueSemaphore = new Semaphore(capacity);
  }

  public void enqueue(int element) throws InterruptedException {
    enqueueSemaphore.acquire();
    q.offer(element);
    dequeueSemaphore.release();
  }

  public int dequeue() throws InterruptedException {
    dequeueSemaphore.acquire();
    final int element = q.poll();
    enqueueSemaphore.release();
    return element;
  }

  public int size() {
    return q.size();
  }

  private Queue<Integer> q = new ArrayDeque<>();
  private Semaphore enqueueSemaphore;
  private Semaphore dequeueSemaphore = new Semaphore(0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
from threading import Semaphore


class BoundedBlockingQueue:
  def __init__(self, capacity: int):
    self.q = collections.deque()
    self.enqueueSemaphore = Semaphore(capacity)
    self.dequeueSemaphore = Semaphore(0)

  def enqueue(self, element: int) -> None:
    self.enqueueSemaphore.acquire()
    self.q.append(element)
    self.dequeueSemaphore.release()

  def dequeue(self) -> int:
    self.dequeueSemaphore.acquire()
    element = self.q.popleft()
    self.enqueueSemaphore.release()
    return element

  def size(self) -> int:
    return len(self.q)