N Queue Using Array

Easy
0/40
Average time to solve is 15m
profile
Contributed by
42 upvotes
Asked in companies
AdobeShopeeAmazon

Problem statement

You will be given ‘N’ queries. You need to implement ‘N’ queues using an array according to those queries. Each query will belong to one of these two types:

1 ‘X’ N: Enqueue element ‘X’  into the end of the nth queue. Returns true if the element is enqueued, otherwise false.

2 N: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.
Note: 
Please note that Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains three space-separated integers ‘N’, ‘S’ and ‘Q’ denoting the number of queues, the size of the array and number of queries, respectively. 

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure.

Each query contains an integer ‘P’ denoting the type of query.

For query of type 1, the integer ‘P’ is equal to 1 and it is followed by two space-separated integers ‘X’ and ‘M’ denoting the element and queue on which operation is to be performed, respectively.

For query of type 2, the integer ‘P’ is equal to 2 and it is followed by a single integer ‘M’ denoting the queue on which operation is to be performed.
Output Format: 
For each query, return the output returned after performing the corresponding operation on the data structure. 

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything, It has already been taken care of. You Just have to complete the given functions.
Constraints: 
1 <= N <= S <= 1000
1 <= Q <= 10^5 
1 <= P <= 2
1 <= X <= 10^5

Time limit: 1 sec
Sample Input 1:
2 5 5
1 2 1 
1 3 2 
1 4 1
2 2
2 1
Sample Output 1:
True 
True
True
3
2
Explanation of Sample Output 1:
For this input, we have the number of queues, 'N' = 2, size of the array, 'S' = 5, and number of queries, 'Q' = 5.

Operations performed on the queue are as follows:

push(2, 1): Push element ‘2’ into the 1st queue. This returns true.
push(3, 2): Push element ‘3’ into the 2nd queue. This returns true.
push(4, 1): Push element ‘4’ into the 1st queue. This returns true.
pop(2): Pop the top element from the 2nd queue. This returns 3.
pop(1): Pop the top element from the 1st queue. This returns 2.
Sample Input 2:
3 10 7
1 11 1
1 51 2
1 26 3 
1 16 2
1 5 3
2 2 
2 3
Sample Output 2:
True 
True
True
True
True
51
26
Explanation for Sample Output 2:
For this input, we have the number of queues, 'N' = 3, size of the array, 'S' = 10, and number of queries, 'Q' = 7.

Operations performed on the queue are as follows:

push(11, 1): Push element ‘11’ into the 1st queue. This returns true.
push(51, 2): Push element ‘51’ into the 2nd queue. This returns true.
push(26, 3): Push element ‘26’ into the 3rd queue. This returns true.
push(16, 2): Push element ‘16’ into the 2nd queue. This returns true.
push(5, 3): Push element ‘5’ into the 3rd queue. This returns true.
pop(2): Pop the top element from the 2nd queue. This returns 51.
pop(3): Pop the top element from the 1st queue. This returns 26.
Hint

Can you think of using some more arrays?

Approaches (1)
Using Extra Arrays

One approach that you might be thinking of is to divide the complete array into ‘N’ parts. Like if there are 3 queues that you need to implement in a single array of size 12, then you divide the array into ‘S’ / ‘N’ = 12 / 3 = 4 parts of equal size and then implement a single queue in different arrays. But, this approach will not be valid for all cases, that is it will give ‘overflow’ and ‘underflow’ conditions even if it is possible to solve those conditions. 

 

Example:

 

‘N’ = 3

‘S’ = 12

‘QUERIES’:  1 1 4 1 1 5 1 1 6 1 1 7 1 1 8

Now, in this case, we divide the array into 3 parts of size = 4 each. Now if we enqueue elements 4 5 6 7 into the first queue and then try to enqueue 8 into the same, the array will show filled and the problem will return the ‘Overflow’ condition even when the array still has empty spaces where the element could be enqueued. 

This makes this approach limited.

 

So, now we will work on a better approach that would solve this problem.

 

In this approach, we will use three arrays to store different indexes, which will help us to implement N queues into a single main array. Let us call these three arrays as start[], end[], next[].

 

The start array will store the indexes of the front elements of all the queues. The end array will store the indexes of the rear elements of all the queues. And finally, the next array will store the indexes of the next value for all values of the main array.

 

Apart from these, we will also initialize a stack that will store the indexes of the empty slots in the main array. Empty slots are the slots that are not yet filled. We will also store the top of this stack as a variable let’s say ‘TEMP’.

 

Now, after initializing all these data structures required, we move on to the algorithm part.

 

Algorithm: 

 

We need to complete two functions enqueue() and dequeue():

 

  1. enqueue(): (Function to enqueue an element into the given queue)
    • Check if the array is full.
      • If yes -> Overflow condition -> return -1
      • Else -> move forward.
    • Store index of the first empty slot from the temp variable to another variable let's say ‘INDEX’.
    • Update the index of the empty slot to the index of the next slot in the empty list.
    • Check if the queue is empty.
      • If yes, update the start element.
      • If no, update the next element of the end.
    • Update the next element and the end element for the given queue.
    • Finally, enqueue the value into the main array.
  2. dequeue(): (Function to dequeue the front element from the given queue)
    • Check if the array is already empty.
      • If yes -> Underflow condition -> return -1
      • Else -> move forward.
    • Find the index of the front element of the given queue and store it in a variable let’s say front.
    • Change the top of the stack to store the next element of the previous top element.
    • Now, attach the previous front element to the beginning of the empty list.
    • Finally, return the previous front element.
Time Complexity

O(1)

 

Both enqueue and dequeue operation takes O(1) time complexity.

Space Complexity

O(N), where ‘N’ is the size of the array.

 

Stacks and arrays for various purposes in the approach makes the space complexity to be O(N). But, even after using this space complexity, this approach is still best because it does not waste any space.

Code Solution
(100% EXP penalty)
N Queue Using Array
Full screen
Console