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
public class KQueues {
int k, n;
int[] arr; // Array of size n to store actual content to be stored in queues
int[] front; // Stores front index of queues
int[] rear; // Stores rear index of queues
int[] 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 itself
int free; // To store the first free space index
KQueues(int k, int n) {
this.k = k;
this.n = n;
this.arr = new int[n];
this.front = new int[k];
this.rear = new int[k];
this.next = new int[n];
// Initialize all queues as empty
for (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-1
private void enqueue(int item, int i) {
// If no free space is available
if (free == -1) {
System.out.println("queue overflow");
return;
}
// Next free slot
int nextFree = next[free];
// If this is the first element in the stack
if (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-1
private int dequeue(int i) {
// If the queue is empty
if (front[i] == -1) {
System.out.println("Stack underflow");
return Integer.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 queue
return arr[frontIndex];
}
}