1188. Design Bounded Blocking Queue

Option 1: condition

while not predicate():
    cv.wait()

wait_for(predicate)

quoted from java multithreading https://howtodoinjava.com/java/multi-threading/wait-notify-and-notifyall-methods/

if a notifier calls notify() on a resource but the notifier still needs to perform 10 seconds of actions on the resource within its synchronized block, the thread that had been waiting will need to wait at least another additional 10 seconds for the notifier to release the lock on the object, even though notify() had been called.

from threading import Condition
class BoundedBlockingQueue(object):

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.queue = collections.deque()
        self.condition = Condition()

    def enqueue(self, element: int) -> None:
        with self.condition:
            self.condition.wait_for(lambda: len(self.queue) < self.capacity)
            self.queue.append(element)
            self.condition.notifyAll()

    def dequeue(self) -> int:
        with self.condition:
            self.condition.wait_for(lambda: len(self.queue) > 0)
            val = self.queue.popleft()
            self.condition.notifyAll()
            return val

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

Option 2: semaphore

from threading import Semaphore

class BoundedBlockingQueue(object):

    def __init__(self, capacity: int):
        self.pushing = Semaphore(capacity)
        self.pulling = Semaphore(0)
        self.queue = collections.deque()

    def enqueue(self, element: int) -> None:
        self.pushing.acquire()
        self.queue.append(element)
        self.pulling.release()

    def dequeue(self) -> int:
        self.pulling.acquire()
        val = self.queue.popleft()
        self.pushing.release()
        return val

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

python deque is thread safe. If deque is not thread safe, we should acquire a lock whenever performing append/popleft against deque

import threading

class BoundedBlockingQueue(object):
    def __init__(self, capacity: int):
        self.capacity = capacity
        
        self.pushing = threading.Semaphore(capacity)
        self.pulling = threading.Semaphore(0)
        self.editing = threading.Lock()
      
        self.queue = collections.deque()

    def enqueue(self, element: int) -> None:
      self.pushing.acquire()
      self.editing.acquire()
      
      self.queue.append(element)
      
      self.editing.release()
      self.pulling.release()

    def dequeue(self) -> int:
        self.pulling.acquire()
        self.editing.acquire()
        
        res = self.queue.popleft()
        
        self.editing.release()
        self.pushing.release()
        return res

    def size(self) -> int:

1188. Design Bounded Blocking Queue - cocoder39/coco39_LC GitHub Wiki