Design Bounded Blocking Queue - Leetcode Solution

Designing a bounded blocking queue is a common problem in concurrent programming. The problem can be stated as follows:

Design a blocking queue that has a fixed capacity and supports the following operations:

1. enqueue(item) - adds an item to the back of the queue
2. dequeue() - removes and returns the item at the front of the queue
3. size() - returns the current number of items in the queue

The enqueue operation should block if the queue is full, and the dequeue operation should block if the queue is empty.

To solve this problem, we can use the following implementation:

import threading

class BoundedBlockingQueue:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = []
        self.lock = threading.Lock()
        self.not_full = threading.Condition(self.lock)
        self.not_empty = threading.Condition(self.lock)

    def enqueue(self, item: int) -> None:
        with self.not_full:
            while len(self.queue) == self.capacity:
                self.not_full.wait()
            self.queue.append(item)
            self.not_empty.notify()

    def dequeue(self) -> int:
        with self.not_empty:
            while len(self.queue) == 0:
                self.not_empty.wait()
            item = self.queue.pop(0)
            self.not_full.notify()
            return item

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

We first declare the class and define the capacity, queue, lock, not_full and not_empty data structures. We use the Python threading module to provide synchronization for concurrent execution.

Next, we define the enqueue() and dequeue() methods. In the enqueue() method, we use the not_full Condition variable to wait until the queue has space for a new item. Once the queue has space, we append the item to the queue and notify any waiting threads that the queue is not empty. In the dequeue() method, we use the not_empty Condition variable to wait until the queue is not empty. Once an item is available, we remove it from the front of the queue, notify any waiting threads that the queue is not full, and return the item.

Finally, we implement the size() method, which simply returns the length of the queue.

Overall, this implementation ensures that the enqueue() and dequeue() operations are thread-safe and that the queue is bounded. It also implements blocking behavior when the queue is full or empty.

1