K queues in an array (2024)

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

In this article, we have explained 2 approaches to implement K queues in a single array. The challenge is that the space of the array should be utilized optimally by the K queues.

Table of content

Method A
A1. A simple approach
A2. Algorithm
A3. Time & Space complexity
A4. A way of implementation

Method B
B1. An efficient approach
B2. Algorithm
B3. Time & Space complexity
B4. A way of implementation

Pre-requisites:

Method A

A1. A simple approach

As we could see in this article implementing 2 queues in an array required implementing 2 push and pop methods for each queue in the array.
How about doing this hard coding for k queues ? Doesn't sound too good, right ?
A logical approach to solve this is to use another parameter k representing the queue that needs to be modified and sending it to the push and pop methods.
But that will not be sufficient since we do not know exactly the heads of the k queues. So, we must calculate them. Since we cannot have a hard coded variables the only way is to use an array that will store the indexes for the queues.

The simplest way to do that is to see if there are remained elements that don't belong to any queue, and that because an array might have even or odd numbers of elements. The number of them can be simple to find by using the mod function and then increase the index of the first rest number of queues by 1.

For example:

having an array of 6 elements and 3 queues will mean that each queue will have 2 elements with the head indexes for the queues [2,4,6]
having an array of 5 elements and 3 queues will mean that not all the queues will be equals. We will have in this case 2 elements unallocated, so the last queue will have with 1 element less than the first ones having the head indexes for the queues [2,4,5]

The downsize of this approach is that it is space inefficient, meaning the size of the queues are fixed and if we want to insert one element in a full queue we cannot do that even though there are free spaces in other queues.

A2. Algorithm

The algorithm for push and pop methods will be the same as in the mentioned article the only difference consisted in calculating the indexes for each queue.
For that we are going to use 2 arrays:

one for storing the heads of each queue
one for storing the movement of elements inside each queue

Pseudo code for calculating the indexes of the k queues

 if k > 0 and sizeArray >= k sizeQueue = sizeArray / k; sizeRest = sizeArray mod k; array idxQk[k] that will store the moved index of the k queue array idxQh[k] that will store the head index of the k queue i = 0; loop if i < sizeRest idxQk[i] <- sizeQueue +1; idxQh[i] <- idxQk[i]; i <- i+1 end loop i = sizeRest; loop if i < k idxQk[i] <- sizeQueue ; idxQh[i] <- idxQk[i]; i <- i+1; end loop

A3. Time & Space complexity

For calculating indexes for k queues the time and space will be O(n).
For push method the time will be O(1) since we are doing one operation.
For pop method the time will be O(n) since we are moving elements.

A4. A way of implementation

#include <iostream>using namespace std;class kQueuesArray{ private: int *v, sizeV, sizeQ, sizeR, *idxQk, *idxQh; public: kQueuesArray(int size, int k) {int i; if (size > 0) { v = new int[size]; sizeV = size; if (k > 0 && size >= k) sizeQ = sizeV / k; sizeR = sizeV % k; idxQk = new int [k]; //store the moved index of the k queue idxQh = new int [k]; //store the head index of the k queue for (i = 0; i < sizeR; i++) { idxQk[i] = (i-1 >= 0 ? idxQk[i-1] : 0 ) + sizeQ +1; idxQh[i] = idxQk[i]; } for (i = sizeR ; i < k; i++) { idxQk[i] = (i-1 >= 0 ? idxQk[i-1] : 0 ) + sizeQ ; idxQh[i] = idxQk[i]; } /* some languages start indexing arrays with 0 so we need to adjust calculated indexes by decreasing them with 1 */ for (i = 0; i < k; i++) { idxQk[i]--; idxQh[i] = idxQk[i]; } } } void pushQk(int elem, int Qk) { if (v[idxQk[Qk-1]]==0 && idxQk[Qk-1] >= 0 ) v[idxQk[Qk-1]--] = elem; //else Queue k is full } int popQk(int Qk) { int temp; if ( v[idxQh[Qk-1]] ) { temp = v[idxQh[Qk-1]] ; if(idxQk[Qk-1] < idxQh[Qk-1]-1 ) for (int i=idxQh[Qk-1]; i-1 > idxQk[Qk-1] ;i--) //move all the elements to the right { v[i] = v[i-1]; v[i-1] = 0; } else v[idxQh[Qk-1]] = 0; idxQk[Qk-1]++; } //else Queue k is empty return temp; } void coutV() { for (int i=0;i<sizeV;i++) cout<<"v["<<i<<"]="<<v[i]<<" "; cout<<endl; } };int main(){ kQueuesArray a(5,3); a.pushQk(11,1); a.pushQk(12,1); a.pushQk(13,1); a.pushQk(21,2); a.pushQk(22,2); a.pushQk(31,3); a.coutV(); cout<<a.popQk(2)<<endl; a.coutV(); a.pushQk(23,2); a.coutV(); cout<<a.popQk(3)<<endl; a.coutV(); a.pushQk(32,3); a.coutV(); return 0;}

Step by step example

Method B

B1. An efficient approach

As we could see from the previous method, again, size of the k queues are fixed in size.
Can we find a way to store elements in an array in such a way to store them dynamically?
As we could see in the 2-nd method from the mentioned article, an array has only 2 heads and we could implemented the efficient storing of elements only for 2 queues.
So, that approach will not work for k queues.
What if we will use the pointer arithmetic logic and store for each element in the array the next element from the k queue that points to it ?

As you could see in the image, the elements that belong to same queue are not store side by side as in previous methods.
The main logic of this approach is to store for each queue, the front, the rear and the next elements inside of it.

B2. Algorithm

Initialization

front and rear arrays are initialized with -1 indicating the empty queues
next array will be initialize with the next index in the array except for the last element which will be -1 indicating nothing to point to.
empty_slot a variable which stores the index of next empty slot in the array, at first will be 0

push(elem, k)

 if empty_slot != -1 array[empty_slot] <- elem last_empty_slot = empty_slot last_front = front[k] front[k] <- empty_slot if rear[k] == -1 rear[k] <- empty_slot empty_slot <- next[empty_slot]; next[last_empty_slot] = -1; if (front[k] != fear[k]) next[last_front] = last_empty_slot; else queue k is full

Since push is a forward implementation:

front will store the current empty slot
rear will store also the current empty slot if it was empty and nothing else if the queue already has a rear head
next will store -1 if the element is the last head in the queue or it doesn't belong to any queue, else the index of the next element
empty_slot will store the next available slot in the array

pop(k)

 if rear[k] != -1 array[rear[k]] <- nil last_rear = rear[k] if next[rear[k]] == -1 front[k] <- -1 rear[k] <- next[rear[k]] empty_slot <- last_rear idxNext[last_rear] <- -1 else queue k is empty

Since pop is a backward implementation:

front will store -1 if the next rear head is empty else nothing to change
rear will store the next rear head
next will store -1 in the last rear element since it doesn't point to anything
empty_slot will store the last rear head

B3. Time & Space complexity

For push method the time will be O(1) since we are doing one operation.
For pop method the time will be O(1) since we are doing one operation.

The space comlexity is O(n).

B4. A way of implementation

 #include <iostream> using namespace std; class kQueuesArray { private: int *v, sizeV, sizeQ, *idxQFront, *idxQRear, *idxNext, empty_slot; public: kQueuesArray(int size, int k) { int i; if (size > 0) { v = new int[size]; sizeV = size; if (k > 0 && size >= k) sizeQ = k; idxQFront = new int [k]; //store the front index of the k queue idxQRear = new int [k]; //store the rear index of the k queue idxNext = new int[size]; for (i = 0; i < k; i++) { idxQFront[i] = idxQRear[i] = -1; } for (i = 0 ; i < size-1; i++) { idxNext[i] = i+1; } idxNext[sizeV-1] = -1; //mark the end of array empty_slot = 0; //mark the next empty slot in the array } } void pushQk(int elem, int Qk) { int last_front, last_empty_slot; if(empty_slot != -1) { v[empty_slot] = elem, last_empty_slot = empty_slot, last_front = idxQFront[Qk-1], idxQFront[Qk-1] = empty_slot, idxQRear[Qk-1] = (idxQRear[Qk-1] == -1 ? empty_slot : idxQRear[Qk-1]), empty_slot = idxNext[empty_slot]; idxNext[last_empty_slot] = -1; if (idxQFront[Qk-1] != idxQRear[Qk-1]) idxNext[last_front] = last_empty_slot; } else cout<<"Queue is full"<<endl; } int popQk(int Qk) { int temp, last_rear; if(idxQRear[Qk-1] != -1) temp = v[idxQRear[Qk-1]], v[idxQRear[Qk-1]] = 0, last_rear = idxQRear[Qk-1], idxQFront[Qk-1] = idxNext[idxQRear[Qk-1]] == -1 ? -1: idxQFront[Qk-1], idxQRear[Qk-1] = idxNext[idxQRear[Qk-1]], empty_slot = last_rear, idxNext[last_rear] = -1; else cout<<"Queue is empty"<<endl; return temp; } void coutV() { for (int i=0;i<sizeV;i++) cout<<"v["<<i<<"]="<<v[i]<<" "; cout<<endl; } }; int main() { kQueuesArray a(5,3); a.coutV(); a.pushQk(11,1); a.pushQk(21,2); a.pushQk(12,1); a.pushQk(13,1); a.pushQk(22,2); a.pushQk(31,3); a.coutV(); cout<<a.popQk(1)<<endl; a.coutV(); a.pushQk(23,2); a.coutV(); cout<<a.popQk(1)<<endl; a.coutV(); a.pushQk(24,2); a.coutV(); cout<<a.popQk(1)<<endl; a.coutV(); a.pushQk(31,3); a.coutV(); a.popQk(2); a.coutV(); a.pushQk(32,3); a.coutV(); return 0; }

Step by step example

With this article at OpenGenus, you must have the complete idea of how to implement K queues in an array.