Implement K queues in single Array C++

Here first we are going to understand the problem of how to efficiently implement K Queues in a single array, then we will discuss a solution and then finally we can implement the same in C++.

Implement K stacks in single Array in C++

Problem:

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

Solution:

Here we will use three arrays as following:

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.
3. next[ ]: This is of size n and stores indexes of next item for all items in array arr[].

Here arr[] is the 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 the next slot. Top of the free stack, ‘free’ is initialized as 0.

Now let’s implement the same in C++

Program to implement K queues in single Array:

You can also execute this code on our online compiler.

// A C++ program to demonstrate implementation of k queues in a single 
// array in time and space efficient way 
#include<iostream> 
#include<climits> 
using namespace std; 

// A C++ class to represent k queues in a single array of size n 
class kQueues 
{ 
    // Array of size n to store actual content to be stored in queue 
    int *arr; 

    // Array of size k to store indexes of front elements of the queue 
    int *front; 

    // Array of size k to store indexes of rear elements of queue 
    int *rear; 

    // Array of size n to store next entry in all queues			 
    int *next; 
    int n, k; 

    int free; // To store the beginning index of the free list 

public: 
    //constructor to create k queue in an array of size n 
    kQueues(int k, int n); 

    // A utility function to check if there is space available 
    bool isFull() { return (free == -1); } 

    // To enqueue an item in queue number 'qn' where qn is from 0 to k-1 
    void enqueue(int item, int qn); 

    // To dequeue an from queue number 'qn' where qn is from 0 to k-1 
    int dequeue(int qn); 

    // 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]; 
} 

/* Driver program to test kStacks class */
int main() 
{ 
    // Let us create 3 queue in an array of size 10 
    int k = 3, n = 10; 
    kQueues ks(k, n); 

    // Let us put some items in queue number 2 
    ks.enqueue(15, 2); 
    ks.enqueue(45, 2); 

    // Let us put some items in queue number 1 
    ks.enqueue(17, 1); 
    ks.enqueue(49, 1); 
    ks.enqueue(39, 1); 

    // Let us put some items in queue number 0 
    ks.enqueue(11, 0); 
    ks.enqueue(9, 0); 
    ks.enqueue(7, 0); 

    cout << "Dequeued element from queue 2 is " << ks.dequeue(2) << endl; 
    cout << "Dequeued element from queue 1 is " << ks.dequeue(1) << endl; 
    cout << "Dequeued element from queue 0 is " << ks.dequeue(0) << endl; 

    return 0; 
} 

OUTPUT:

Dequeued element from queue 2 is 15
Dequeued element from queue 1 is 17
Dequeued element from queue 0 is 11

Time Complexity: Time complexities of enqueue() and dequeue() is O(1).

The best part of the above implementation is, if there is a slot available in the queue, then an item can be enqueued in any of the queues, i.e., no wastage of space. This method requires some extra space. Space may not be an issue because queue items are typically large, for example, queues of employees, students, etc. where every item is of hundreds of bytes. For such large queues, the extra space used is comparatively very less as we use three integer arrays as extra space.

Comment in case of any suggestion or improvements.