How to efficiently implement k Queues in a single array?
Create a data structure kQueues that represents k queues. Implementation of kQueues should use only one array, i.e., k queues should use the same array for storing elements. Following functions must be supported by kQueues.
enqueue(int x, int qn) –> adds x to queue number ‘qn’ where qn is from 0 to k-1
dequeue(int qn) –> deletes an element from queue number ‘qn’ where qn is from 0 to k-1
publicclassKQueues {int k, n;int[] arr; // Array of size n to store actual content to be stored in queuesint[] front; // Stores front index of queuesint[] rear; // Stores rear index of queuesint[] next; // next[i] will store the next free space if you want to occupy this space in// original array otherwise it something already is present at this index, then// it will store the index of next element in the queue OR -1 if it// is the last element itselfint free; // To store the first free space indexKQueues(int k,int n) {this.k= k;this.n= n;this.arr=newint[n];this.front=newint[k];this.rear=newint[k];this.next=newint[n];// Initialize all queues as emptyfor (int i =0; i < k; i++) { front[i] = rear[i] =-1; }// Initialize all spaces as free free =0;for (int i =0; i < n -1; i++) next[i] = i +1; next[n -1] =-1; // Last index has no free space after it }// To enqueue an item in queue number 'i' where i is from 0 to k-1privatevoidenqueue(int item,int i) {// If no free space is availableif (free ==-1) {System.out.println("queue overflow");return; }// Next free slotint nextFree = next[free];// If this is the first element in the stackif (front[i] ==-1) rear[i] = front[i] = free;// Update next of rear and then rear for queue number 'i'else { next[rear[i]] = free; rear[i] = free; } next[free] =-1;// Put the item in array arr[free] = item;// Update index of free slot to index of next slot in free list free = nextFree; }// To dequeue an from queue number 'i' where i is from 0 to k-1privateintdequeue(int i) {// If the queue is emptyif (front[i] ==-1) {System.out.println("Stack underflow");returnInteger.MIN_VALUE; }// Find index of front item in queue number 'i'int frontIndex = front[i];// Change top to store next of previous top front[i] = next[frontIndex];// Attach the previous front to the beginning of free list next[frontIndex] = free; free = frontIndex;// return top of queuereturn arr[frontIndex]; }}