Last Updated: 19 Mar, 2021
Bounded Blocking Queue
Moderate
Asked in companies
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.
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
Approaches
- 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
- 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.