Bounded Blocking Queue

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
9 upvotes
Asked in companies
eBayUber

Problem statement

Implement a bounded blocking queue that has the following functions:

BoundedBlockingQueue( int capacity ): Creates a queue of the given capacity.

Void Enqueue(int val): Adds an element to the end of the queue. If the queue is full, enqueue request gets blocked until the queue has no empty space i.e the element is stored at some other space and enqueued in the list when there is space in the queue.  

Int Dequeue(): Returns the element at the front of the queue and blocks the dequeue request if there are no items in the queue until the queue has an element enqueued.

Int Size(): Returns the size of the queue.

You will be given ‘Q’ queries. You need to implement a bounded blocking queue according to those queries. Each query will belong to one of these two types:

0 ‘C’: Creates a queue of a capacity ‘C’.

1 ‘X’: Enqueue element ‘X’  into the end of the queue. 

2: Dequeue the element at the front of the queue. 
Returns -1 if the queue is empty, otherwise, returns the dequeued element.

3: Returns the size of the queue.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains ‘T’ denoting the number of the test cases.

Each of the test cases is described as:

The first line contains ‘Q’ denoting the number of queries to be answered.

The next ‘Q’ lines specify the type of query to be performed as mentioned above.
Output Format : 
For each test case, for all the query of type:-

2: Return -1 if the queue is empty otherwise return the dequeued element.

3: Returns the size of the queue.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= Q <= 10^5 
0 <= P <= 3
1 <= X <= 10^5

Where 'P’, denotes the type of query.‘X’ is the element to be enqueued in case the query type is ‘1’.

Time Limit : 1sec
Sample Input 1 :
2
7
0 5
1 3
1 9
2 
3
2
3
4
0 2
2
1 7
3
Sample Output 1 :
3 1 9 0
-1 7 0
Explanation Of Sample Input 1 :
Test Case 1:  For this input, we have number of queries, Q = 7.
Operations performed on the queue are as follows:
0 5 -> A queue of capacity ‘5’ is initialized.
1 3-> Enqueue 1 to back of the queue. q= [3]
1 9 -> Enqueue 9 to back of queue. q= [3,9]
2 -> Dequeue front element and return 3 . q= [ 9 ].
3 -> Return size of queue i.e 1.
2-> Dequeue front element. q= [ ].
3 -> Return the size of the queue. I.e 0.

Test Case 2: For this input, we have the number of queries, Q = 4.
0 2 -> A queue of capacity ‘2’ is initialized.
2 -> We have to dequeue an element but as the queue is empty this request will go to a blocked state and return -1.
1 7 -> Enqueue 7 to the queue. Now the blocked request of dequeue will be unblocked So dequeue front element i.e ‘7’ and return it. 
3 -> Return the size of the queue i.e ‘0’.
Sample Input 2 :
2
2
0 8
2
3
0 11
1 4
1 21
Sample Output 2 :
-1
Hint

Think of the blocked requests, maybe we can use a separate queue to handle them.

Approaches (1)
Queue Implementation
  • A bounded queue is the same as a normal queue but unlike a normal queue, it sends the enqueue or dequeue requests to block the state if the queue is full or empty.
  • We will take a queue ‘waiting’ that will store the elements that are in a blocked state for being enqueued in the list and a variable ‘pending’ that keeps the count of the ‘deque’ requests that are in a blocked state.
  • Now when an enqueue request arrives, if the queue has no space, we will add the element to the back of the ‘waiting’ queue. otherwise, we will add the element to our Bounded building queue. Now if pending >0 i.e if there is any dequeue request that is in a blocked state, we will dequeue the element at the front.
  • Similarly for dequeue, if the queue is empty we will increment the count of ‘pending’ otherwise we will dequeue the element at front of the queue. Now if there are elements in the ‘waiting’ queue then we can add the element at front of it as the dequeue operation empty the space.

 

Algorithm

 

  1. Enqueue

 

  • If the size of the queue becomes equal to the capacity of the queue.
    • Add the element to the back of the ‘waiting’ queue.
  • Otherwise
    • Add the element to the BoundedBlockingQueue.
  • If pending > 0
    • Dequeue the element at the front of BoundedBlockingQueue.
    • Decrement ‘pending’ as one of the pending requests is executed.

 

2. Dequeue

 

  • If the size of the queue is 0
    • Increment ‘pending’
  • Otherwise
    • Dequeue element at front of the queue.
  • If the size of the ‘waiting’ queue is greater than 0.
    • Dequeue element at front of the ‘waiting’ queue and enqueue it to the end of BoundedBlockingQueue.

3. Size

 

  • Returns the size of the queue.
Time Complexity

O(Q), where ‘Q’ is the number of queries to be performed.

 

As Enqueue and dequeue operation takes O(1) time. Therefore for ‘Q’ queries, time complexity will be O(Q).

Space Complexity

O(Q), where ‘Q’ is the number of queries to be performed.

 

We are using a ‘waiting’ queue that will store elements that are in a blocked state for being enqueued in the queue. The maximum number of elements in the blocked state will be equal to the number of queries. Therefore space complexity will be O( Q ).

Code Solution
(100% EXP penalty)
Bounded Blocking Queue
Full screen
Console