How to efficiently implement k Queues in a single array? - GeeksforGeeks
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
Read full article from How to efficiently implement k Queues in a single array? - GeeksforGeeks
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
The idea is similar to the stack post, here we need to use three extra arrays. In stack post, we needed to extra arrays, one more array is required because in queues, enqueue() and dequeue() operations are done at different ends.
Following are the three extra arrays are used:
1) front[]: This is of size k and stores indexes of front elements in all queues.
2) rear[]: This is of size k and stores indexes of rear elements in all queues.
2) next[]: This is of size n and stores indexes of next item for all items in array arr[].
1) front[]: This is of size k and stores indexes of front elements in all queues.
2) rear[]: This is of size k and stores indexes of rear elements in all queues.
2) next[]: This is of size n and stores indexes of next item for all items in array arr[].
Here arr[] is actual array that stores k stacks.
Together with k queues, a stack of free slots in arr[] is also maintained. The top of this stack is stored in a variable ‘free’.
All entries in front[] are initialized as -1 to indicate that all queues are empty. All entries next[i] are initialized as i+1 because all slots are free initially and pointing to next slot. Top of free stack, ‘free’ is initialized as 0.
class
kQueues
{
int
*arr;
// Array of size n to store actual content to be stored in queue
int
*front;
// Array of size k to store indexes of front elements of queue
int
*rear;
// Array of size k to store indexes of rear elements of queue
int
*next;
// Array of size n to store next entry in all queues
// and free list
int
n, k;
int
free
;
// To store beginning index of free list
public
:
bool
isFull() {
return
(
free
== -1); }
// To check whether queue number 'qn' is empty or not
bool
isEmpty(
int
qn) {
return
(front[qn] == -1); }
};
// Constructor to create k queues in an array of size n
kQueues::kQueues(
int
k1,
int
n1)
{
// Initialize n and k, and allocate memory for all arrays
k = k1, n = n1;
arr =
new
int
[n];
front =
new
int
[k];
rear =
new
int
[k];
next =
new
int
[n];
// Initialize all queues as empty
for
(
int
i = 0; i < k; i++)
front[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;
// -1 is used to indicate end of free list
}
// To enqueue an item in queue number 'qn' where qn is from 0 to k-1
void
kQueues::enqueue(
int
item,
int
qn)
{
// Overflow check
if
(isFull())
{
cout <<
"\nQueue Overflow\n"
;
return
;
}
int
i =
free
;
// Store index of first free slot
// Update index of free slot to index of next slot in free list
free
= next[i];
if
(isEmpty(qn))
front[qn] = i;
else
next[rear[qn]] = i;
next[i] = -1;
// Update next of rear and then rear for queue number 'qn'
rear[qn] = i;
// Put the item in array
arr[i] = item;
}
// To dequeue an from queue number 'qn' where qn is from 0 to k-1
int
kQueues::dequeue(
int
qn)
{
// Underflow checkSAS
if
(isEmpty(qn))
{
cout <<
"\nQueue Underflow\n"
;
return
INT_MAX;
}
// Find index of front item in queue number 'qn'
int
i = front[qn];
front[qn] = next[i];
// Change top to store next of previous top
// Attach the previous front to the beginning of free list
next[i] =
free
;
free
= i;
// Return the previous front item
return
arr[i];
}