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:
- Queue data structure
- Basics of Array
- 2 queues in one array
- K stacks in one array
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 loopA3. 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 fullSince 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.
