Tiny System Design part 2

Part 1 can be found here.

1188. Design Bounded Blocking Queue

• Naive and WRONG solution

class BoundedBlockingQueue(object):
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._q = collections.deque([])
    def enqueue(self, element: int) -> None:
        if len(self._q)==self._capacity:return
        self._q.append(element)
    def dequeue(self) -> int:
        if not self._q:return -1
        return self._q.pop()
    def size(self) -> int:
        return len(self._q)

• Good solution

This solution is from here.

“The idea is to use two semaphores, pushing and pulling, to maintain the invariants of the queue.
Initially, no thread can dequeue (self.pulling.acquire()) until a thread has enqueued (self.pulling.release()).
When capacity elements have been enqueued, self.pushing.acquire() will block the thread until a dequeue releases the semaphore again.
Additionally, use a Lock so only a single thread can modify the actual queue at once.”

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:
      return len(self.queue)

As the collections.deque is thread safe, the self.editing is unnecessary.

import threading
class BoundedBlockingQueue(object):
    def __init__(self, capacity: int):
        self._capacity = capacity
        self._queue = collections.deque()
        self._pushing = threading.Semaphore(capacity)
        self._pulling = threading.Semaphore(0)
    def enqueue(self, element: int) -> None:
        self._pushing.acquire()
        self._queue.append(element)
        self._pulling.release()
        
    def dequeue(self) -> int:
        self._pulling.acquire()
        res = self._queue.popleft()
        self._pushing.release()
        return res
    def size(self) -> int:
        return len(self._queue)