How to Efficiently Implement k Queues in a Single Array? (2024)

In some cases, we need to implement our own data structure for better usability and customization. Here, we need to implement the K Queues using the single array.

The first solution that comes to mind is dividing the array into N/K parts and using each part of the array as a queue. Here, N is the array length. The problem with this solution is that we can’t utilize the array's space properly. If the array is not full, but any Mth queue indexes are full, we can’t insert an element to the Mth queue. So, we need an optimized approach.

The efficient approach uses the circular array to avoid wasting the array space. We can connect each array element to the next element using the next[] array. So we can get the next element of the current queue. We can start a new queue with any empty slot if we want to start a new queue.

Problem statement − We have given an array of length N. We need to implement the K queues in the given array.

Approach 1

This approach will use the que_arr[] to store the queue elements. Also, we will use the three arrays below to track the queue elements.

• start[] = To store the starting pointer of each queue.

• last[] = To store the last pointer of each queue.

• next[] = To store the next pointer of each element of each queue.

Here, we can use any free slots to start a new queue, and we will present free slots with −1 in the next[] array. Also, we will implement the functionalities to check whether the queue is empty or full.

Algorithm

Step 1 − Define the ‘customQueue’ class. Inside the ‘customQueue’ class, define the ‘que_arr’, ‘start’, ‘last’, and ‘next’ pointers of integer type. Also, define the n and k to store the array length, the total number of queues, and the ‘freeslot’ variable to track the next index of the available slot.

Step 2 − Also, declare the constructor and methods into the class.

Step 3 − Next, define the member functions of the class. First, we will define the constructor for the class.

Step 3.1 − Initialize the n and K variables. Also, initialize the que_arr and next pointer with the array of length N, and start and last pointer with the array of the length K.

Step 3.2 − Update all values of the start[] array with −1, as all indexes are available to start the queue. Also, update the ‘freeSlot’ with 0.

Step 3.3 − Next, update the next[p] with p + 1 to connect each element with the next element.

Step 4 − Now, define the enq() member function to insert an element into any queue. It takes the element and que number as a parameter.

Step 4.1 − If the queue is full, print the message accordingly. If the freeSlot value is −1, the que is full.

Step 4.2 − Otherwise, store the ‘freeSlot’ value in p to get the next free slot.

Step 4.3 −Update the ‘freeSlot’ with the next[p], representing the next pointer of the current slot.

Step 4.4 − If the queue is empty, update the start[q_num] with p. Else, update the next[last[q_num]] with p.

Step 4.5 − Update the next[p] with −1. Also, update the last pointer of the current queue with the ‘p’ and add the given element at the ‘p’ index in que_arr.

Step 5 − Define the deq() function to remove the element from any queue.

Step 5.1 − If the queue is empty, print the message accordingly. If start[q_num] is −1, we can say the queue is empty.

Step 5.2 − Get the starting pointer of the queue, and update the start pointer with the next pointer as we need to remove the first element of the queue.

Step 5.3 − Update the next[p] with the ‘freeslot’ value and ‘freeslot’ with the p.

Step 5.4 − Return the que_arr[p] element.

Step 6 − In the main() function, use the enq() method to add different values to the different queues.

Step 7 − After that, execute the deq() method for each queue and observe the output.

Example

#include <iostream>#include <climits>using namespace std;// Class to create a custom queueclass customQueue { // Array for a queue int *que_arr; // start pointer int *start; // End ponter int *last; // Next pointer int *next; int n, k; // For storing indexes of free slots in que_arr int freeslot;public: // Constructor customQueue(int k, int n); // To check whether any space is available or not bool isQueFull() { return (freeslot == -1); } // Method declaration to enqueue an ele void enq(int ele, int q_num); // Method declaration to dequeue an ele int deq(int q_num); // For checking whether queue number 'q_num' is empty or not bool isQueueEmpty(int q_num) { return (start[q_num] == -1); }};// Constructor to create k queues in an array of size ncustomQueue::customQueue(int totalQueues, int arr_len) { // Initialize n and k, and allocate // memory for all arrays k = totalQueues, n = arr_len; que_arr = new int[n]; start = new int[k]; last = new int[k]; next = new int[n]; // Initially, all queues are available for (int p = 0; p < k; p++) start[p] = -1; freeslot = 0; // Connect current slot with next slot for (int p = 0; p < n - 1; p++) next[p] = p + 1; next[n - 1] = -1; // last slot is free slot}void customQueue::enq(int ele, int q_num) { if (isQueFull()) { cout << "
Queue is full!
"; return; } // Get an index of free slot int p = freeslot; // Current slot is filled. So, the next slot will be free freeslot = next[p]; // Set the index of the free slot as start if the queue is empty1 if (isQueueEmpty(q_num)) start[q_num] = p; else next[last[q_num]] = p; // Next slot is last pointer of current queue next[p] = -1; // mark as a free slot // last pointer for the current queue last[q_num] = p; // Enqueue element que_arr[p] = ele;}int customQueue::deq(int q_num) { if (isQueueEmpty(q_num)) { cout << "
Queue is empty!
"; return INT_MAX; } // get the start index int p = start[q_num]; // We remove the first element from the queue. So, the next of the current element will be the starting point of the queue start[q_num] = next[p]; // Update the next slot with a free slot next[p] = freeslot; freeslot = p; // return the element return que_arr[p];}int main() { // queue of size 4 and array of size 15 int k = 4, n = 15; customQueue que(k, n); // Insert in first queue que.enq(54, 0); que.enq(98, 0); // Insert in second queue que.enq(93, 1); que.enq(23, 1); que.enq(12, 1); // Insert in third queue que.enq(1, 2); que.enq(97, 2); que.enq(27, 2); // Insert in fourth queue que.enq(54, 3); que.enq(23, 3); que.enq(65, 3); cout << "After removing the element from 1st queue is " << que.deq(1) << endl; cout << "After removing the element from 2nd queue is " << que.deq(2) << endl; cout << "After removing the element from 0th queue is " << que.deq(0) << endl; cout << "After removing the element from 3rd queue is " << que.deq(3) << endl; return 0;}

Output

After removing the element from 1st queue is 93After removing the element from 2nd queue is 1After removing the element from 0th queue is 54After removing the element from 3rd queue is 54

Time complexity − O(1) for the enqueue and deque.

Space complexity − O(N) to store the elements in a queue.

The K queue implementation using the circular array saves space, but we need to handle each queue's start, end, and next pointer perfectly. Otherwise, it can give random errors.

However, it is more complex to implement than the naïve approach, but saving memory is most important in real0−time development.