We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Bounded Blocking Queue

Number: 1209

Difficulty: Medium

Paid? Yes

Companies: LinkedIn

Problem Description

Implement a thread-safe, bounded blocking queue with methods to enqueue and dequeue elements. The enqueue operation adds an element to the front of the queue and blocks if the queue is full until space is available. The dequeue operation removes an element from the rear of the queue and blocks if the queue is empty until an element is available. A size method returns the current number of elements in the queue.

Key Insights

  • Thread-safety requires proper synchronization (using locks/mutexes).
  • Use two condition variables (or equivalent) to block threads when the queue is empty or full.
  • The underlying data structure can be a deque (double-ended queue) for efficient insertions at the front and removals from the rear.
  • Notify waiting consumer threads after an enqueue and waiting producer threads after a dequeue.
  • Each operation (enqueue, dequeue, size) must use mutual exclusion to avoid race conditions.

Space and Time Complexity

Time Complexity: O(1) per operation (enqueue and dequeue take constant time). Space Complexity: O(capacity), where capacity is the maximum number of elements the queue can hold.

Solution

The approach is to use an underlying queue (such as a deque) and protect it with a lock. Two condition variables are used:

  1. not_full: to make producer threads wait when the queue is full.
  2. not_empty: to make consumer threads wait when the queue is empty. When enqueue is called, the thread acquires the lock, waits on not_full if necessary, adds the element at the front, and then notifies threads waiting on not_empty. When dequeue is called, the thread acquires the lock, waits on not_empty if necessary, removes an element from the rear, and then notifies threads waiting on not_full. The size method simply returns the current size of the underlying container under the lock.

Code Solutions

import threading
from collections import deque

class BoundedBlockingQueue:
    def __init__(self, capacity):
        self.capacity = capacity               # maximum capacity of the queue
        self.queue = deque()                   # underlying deque for the queue
        self.lock = threading.Lock()           # lock for mutual exclusion
        self.not_empty = threading.Condition(self.lock)  # condition variable for consumers
        self.not_full = threading.Condition(self.lock)   # condition variable for producers

    # Adds an element to the front of the queue. Blocks if the queue is full.
    def enqueue(self, element: int) -> None:
        with self.not_full:
            # Wait until queue is not full
            while len(self.queue) >= self.capacity:
                self.not_full.wait()
            # Add element to the front
            self.queue.appendleft(element)
            # Notify one waiting consumer that an element is available
            self.not_empty.notify()

    # Removes and returns the element from the rear of the queue. Blocks if empty.
    def dequeue(self) -> int:
        with self.not_empty:
            # Wait until queue is not empty
            while not self.queue:
                self.not_empty.wait()
            # Remove element from the rear
            element = self.queue.pop()
            # Notify one waiting producer that space is available
            self.not_full.notify()
            return element

    # Returns the current size of the queue.
    def size(self) -> int:
        with self.lock:
            return len(self.queue)
← Back to All Questions