Last Updated : 02 May, 2023
Comments
Improve
Recommended Problem
Implement Queue using array
Companies:
AmazonGoldman Sachs
Show Topics
Topics:
ArraysQueue
+1 more
Solve Problem
Basic
47.24%
1.7L
Introduction :
One efficient way to implement k queues in a single array is to use a technique called “circular array implementation of k queues.” This approach uses a single array to store elements for all k queues, and it divides the array into k segments, one for each queue.
To implement this approach, we need to keep track of two pointers for each queue: a front pointer and a rear pointer. These pointers will indicate the start and end of the segment in the array for each queue. We also need to keep track of the size of each segment to know how many elements are currently in each queue.
To enqueue an element into a particular queue, we need to check if there is any space left in the segment for that queue. If there is space, we can add the element to the end of the segment and update the rear pointer for that queue. If there is no space, we need to return an error or resize the segment (if possible).
To dequeue an element from a particular queue, we need to check if there are any elements in that queue. If there are elements, we can remove the first element in the segment and update the front pointer for that queue. If there are no elements, we need to return an error.
To implement this approach efficiently, we can use a circular array to avoid wasting space. This means that if we reach the end of a segment, we wrap around to the beginning of the segment, effectively treating the array as a circle
We have discussed efficient implementation of k stack in an array. In this post, same for queue is discussed. Following is the detailed problem statement.
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
Method 1 (Divide the array in slots of size n/k):
A simple way to implement k queues is to divide the array in k slots of size n/k each, and fix the slots for different queues, i.e., use arr[0] to arr[n/k-1] for the first queue, and arr[n/k] to arr[2n/k-1] for queue2 where arr[] is the array to be used to implement two queues and size of array be n.
The problem with this method is an inefficient use of array space. An enqueue operation may result in overflow even if there is space available in arr[]. For example, consider k as 2 and array size n as 6. Let we enqueue 3 elements to first and do not enqueue anything to the second queue. When we enqueue the 4th element to the first queue, there will be overflow even if we have space for 3 more elements in the array.
Method 2 (A space efficient implementation):
The idea is similar to the stack post, here we need to use three extra arrays. In stack post, we needed two 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:
- front[]: This is of size k and stores indexes of front elements in all queues.
- rear[]: This is of size k and stores indexes of rear elements in all queues.
- 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.
Following is implementation of the above idea.
C++
// 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];
// Change top to store next of previous top
front[qn] = next[i];
// 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;
}
Java
// A Java program to demonstrate implementation of k queues in a single
// array in time and space efficient way
public class KQueues {
int k;
int n;
int[] arr;
int[] front;
int[] rear;
int[] next;
int free;
KQueues(int k, int n){
// Initialize n and k, and allocate memory for all arrays
this.k = k;
this.n = n;
this.arr = new int[n];
this.front = new int[k];
this.rear = new int[k];
this.next = new int[n];
// Initialize all queues as empty
for(int i= 0; i< k; i++) {
front[i] = rear[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;
}
public static void main(String[] args)
{
// Let us create 3 queue in an array of size 10
int k = 3, n = 10;
KQueues ks= new KQueues(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);
System.out.println("Dequeued element from queue 2 is " +
ks.dequeue(2));
System.out.println("Dequeued element from queue 1 is " +
ks.dequeue(1));
System.out.println("Dequeued element from queue 0 is " +
ks.dequeue(0) );
}
// To check whether queue number 'i' is empty or not
private boolean isEmpty(int i) {
return front[i] == -1;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
private boolean isFull(int i) {
return free == -1;
}
// To enqueue an item in queue number 'j' where j is from 0 to k-1
private void enqueue(int item, int j) {
if(isFull(j)) {
System.out.println("queue overflow");
return;
}
int nextFree = next[free];
if(isEmpty(j)) {
rear[j] = front[j] = free;
}else {
// Update next of rear and then rear for queue number 'j'
next[rear[j]] = free;
rear[j] = free;
}
next[free] = -1;
// Put the item in array
arr[free] = item;
// Update index of free slot to index of next slot in free list
free = nextFree;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
private int dequeue(int i) {
// Underflow checkSAS
if(isEmpty(i)) {
System.out.println("Stack underflow");
return Integer.MIN_VALUE;
}
// Find index of front item in queue number 'i'
int frontIndex = front[i];
// Change top to store next of previous top
front[i] = next[frontIndex];
// Attach the previous front to the beginning of free list
next[frontIndex] = free;
free = frontIndex;
return arr[frontIndex];
}
}
Python3
# A Python program to demonstrate implementation of k queues in a single
# array in time and space efficient way
class KQueues:
def __init__(self, number_of_queues, array_length):
self.number_of_queues = number_of_queues
self.array_length = array_length
self.array = [-1] * array_length
self.front = [-1] * number_of_queues
self.rear = [-1] * number_of_queues
self.next_array = list(range(1, array_length))
self.next_array.append(-1)
self.free = 0
# To check whether the current queue_number is empty or not
def is_empty(self, queue_number):
return True if self.front[queue_number] == -1 else False
# To check whether the current queue_number is full or not
def is_full(self, queue_number):
return True if self.free == -1 else False
# To enqueue the given item in the given queue_number where
# queue_number is from 0 to number_of_queues-1
def enqueue(self, item, queue_number):
if self.is_full(queue_number):
print("Queue FULL")
return
next_free = self.next_array[self.free]
if self.is_empty(queue_number):
self.front[queue_number] = self.rear[queue_number] = self.free
else:
self.next_array[self.rear[queue_number]] = self.free
self.rear[queue_number] = self.free
self.next_array[self.free] = -1
self.array[self.free] = item
self.free = next_free
# To dequeue an item from the given queue_number where
# queue_number is from 0 to number_of_queues-1
def dequeue(self, queue_number):
if self.is_empty(queue_number):
print("Queue EMPTY")
return
front_index = self.front[queue_number]
self.front[queue_number] = self.next_array[front_index]
self.next_array[front_index] = self.free
self.free = front_index
return self.array[front_index]
if __name__ == "__main__":
# Let us create 3 queue in an array of size 10
ks = KQueues(3, 10)
# 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);
print("Dequeued element from queue 2 is {}".format(ks.dequeue(2)))
print("Dequeued element from queue 1 is {}".format(ks.dequeue(1)))
print("Dequeued element from queue 0 is {}".format(ks.dequeue(0)))
C#
// A C# program to demonstrate implementation of k queues in a single
// array in time and space efficient way
using System;
public class KQueues
{
int k;
int n;
int[] arr;
int[] front;
int[] rear;
int[] next;
int free;
KQueues(int k, int n)
{
// Initialize n and k, and
// allocate memory for all arrays
this.k = k;
this.n = n;
this.arr = new int[n];
this.front = new int[k];
this.rear = new int[k];
this.next = new int[n];
// Initialize all queues as empty
for(int i = 0; i < k; i++)
{
front[i] = rear[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;
}
public static void Main(String[] args)
{
// Let us create 3 queue in an array of size 10
int k = 3, n = 10;
KQueues ks = new KQueues(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);
Console.WriteLine("Dequeued element from queue 2 is " +
ks.dequeue(2));
Console.WriteLine("Dequeued element from queue 1 is " +
ks.dequeue(1));
Console.WriteLine("Dequeued element from queue 0 is " +
ks.dequeue(0) );
}
// To check whether queue number 'i' is empty or not
private bool isEmpty(int i)
{
return front[i] == -1;
}
// To dequeue an from queue
// number 'i' where i is from 0 to k-1
private bool isFull(int i)
{
return free == -1;
}
// To enqueue an item in queue
// number 'j' where j is from 0 to k-1
private void enqueue(int item, int j)
{
if(isFull(j))
{
Console.WriteLine("queue overflow");
return;
}
int nextFree = next[free];
if(isEmpty(j))
{
rear[j] = front[j] = free;
}
else
{
// Update next of rear and then
// rear for queue number 'j'
next[rear[j]] = free;
rear[j] = free;
}
next[free] = -1;
// Put the item in array
arr[free] = item;
// Update index of free slot to
// index of next slot in free list
free = nextFree;
}
// To dequeue an from queue
// number 'i' where i is from 0 to k-1
private int dequeue(int i)
{
// Underflow checkSAS
if(isEmpty(i))
{
Console.WriteLine("Stack underflow");
return int.MinValue;
}
// Find index of front item in queue number 'i'
int frontIndex = front[i];
// Change top to store next of previous top
front[i] = next[frontIndex];
// Attach the previous front to the beginning of free list
next[frontIndex] = free;
free = frontIndex;
return arr[frontIndex];
}
}
// This code is contributed by aashish1995
Javascript
<script>
// A Javascript program to demonstrate implementation of k queues in a single
// array in time and space efficient way
class KQueues
{
constructor(k,n)
{
// Initialize n and k, and allocate memory for all arrays
this.k = k;
this.n = n;
this.arr = new Array(n);
this.front = new Array(k);
this.rear = new Array(k);
this.next = new Array(n);
// Initialize all queues as empty
for(let i= 0; i< k; i++) {
this.front[i] = this.rear[i] = -1;
}
// Initialize all spaces as free
this.free = 0;
for(let i= 0; i< n-1; i++) {
this.next[i] = i+1;
}
this.next[n-1] = -1;
}
// To check whether queue number 'i' is empty or not
isEmpty(i)
{
return this.front[i] == -1;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
isFull(i)
{
return this.free == -1;
}
// To enqueue an item in queue number 'j' where j is from 0 to k-1
enqueue(item,j)
{
if(this.isFull(j)) {
document.write("queue overflow<br>");
return;
}
let nextFree = this.next[this.free];
if(this.isEmpty(j)) {
this.rear[j] = this.front[j] = this.free;
}else {
// Update next of rear and then rear for queue number 'j'
this.next[this.rear[j]] = this.free;
this.rear[j] = this.free;
}
this.next[this.free] = -1;
// Put the item in array
this.arr[this.free] = item;
// Update index of free slot to index of next slot in free list
this.free = nextFree;
}
// To dequeue an from queue number 'i' where i is from 0 to k-1
dequeue(i)
{
// Underflow checkSAS
if(this.isEmpty(i)) {
document.write("Stack underflow<br>");
return Number.MIN_VALUE;
}
// Find index of front item in queue number 'i'
let frontIndex = this.front[i];
// Change top to store next of previous top
this.front[i] = this.next[frontIndex];
// Attach the previous front to the beginning of free list
this.next[frontIndex] = this.free;
this.free = frontIndex;
return this.arr[frontIndex];
}
}
// Let us create 3 queue in an array of size 10
let k = 3, n = 10;
let ks= new KQueues(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);
document.write("Dequeued element from queue 2 is " +
ks.dequeue(2)+"<br>");
document.write("Dequeued element from queue 1 is " +
ks.dequeue(1)+"<br>");
document.write("Dequeued element from queue 0 is " +
ks.dequeue(0)+"<br>" );
// This code is contributed by avanitrachhadiya2155
</script>
Output
Dequeued element from queue 2 is 15Dequeued element from queue 1 is 17Dequeued element from queue 0 is 11
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.
Issuses in efficiently implement k Queues in a single array :
While the circular array implementation of k queues is an efficient way to implement multiple queues in a single array, there are several issues that need to be considered to ensure that the implementation is correct and efficient.
- Size allocation: One issue is deciding how to allocate the size of each queue segment in the array. If the size of one queue segment is too small, that queue may fill up quickly, causing a lot of unnecessary resizing and memory allocation. On the other hand, if the size of one queue segment is too large, there may be a lot of wasted space in the array.
- Overflow/underflow: Another issue is handling overflow and underflow. If the array becomes full, there will be no space to enqueue elements, and if the array becomes empty, there will be no elements left to dequeue. It is important to handle these cases properly to avoid errors or unexpected behavior.
- Tracking size: To properly implement the k queues in a single array, we need to keep track of the size of each queue segment to know how many elements are currently in each queue. This can add overhead to the implementation, as we need to update the size of each segment whenever we enqueue or dequeue an element.
- Implementation complexity: Finally, the circular array implementation of k queues can be more complex to implement and maintain than a simpler implementation using separate arrays for each queue. This is because we need to keep track of multiple pointers and manage the circular nature of the array.
Examples of Queues in a single array :
- Multi-Threaded Programming: In multi-threaded programming, where multiple threads need to access shared resources in a concurrent manner, a circular array implementation of k queues can be used to implement a thread-safe data structure. Each thread can access a particular queue, and the queues can be managed in a thread-safe manner.
- Resource Management: In a resource management system, such as a job scheduler or task manager, queues can be used to manage resources efficiently. Using a single array to implement multiple queues allows efficient management of multiple resources.
- Web Servers: In web servers, queues can be used to manage incoming requests from clients. A single array implementation of multiple queues can be used to manage multiple request queues, such as HTTP and FTP requests, in a single data structure.
- Operating Systems: In operating systems, queues can be used to manage system resources such as CPU time and memory. A circular array implementation of multiple queues can be used to manage multiple queues of processes or threads, allowing efficient resource management.
- Data Structures: Queues are a fundamental data structure used in many algorithms and software applications. A circular array implementation of multiple queues can be used to implement queue-based algorithms such as breadth-first search, shortest path algorithms, and simulation algorithms.
GeeksforGeeks
Improve
Previous Article
Queue using Stacks
Next Article
Complete Tutorial on LRU Cache with Implementations
