Stacks & QueuesProblem 24 of 38
Implement n queue in an array
Problem Statement
Design a data structure to implement N queues using a single array of size S. The data structure should support the following operations efficiently:
enqueue(x, qn): Add element x to queue number qn (0 to N-1)dequeue(qn): Remove and return the front element from queue qnisFull(qn): Check if queue qn is fullisEmpty(qn): Check if queue qn is empty
Example:
N = 3 queues, Array size S = 6
enqueue(10, 0) // Add 10 to queue 0
enqueue(20, 0) // Add 20 to queue 0
enqueue(30, 1) // Add 30 to queue 1
enqueue(40, 2) // Add 40 to queue 2
dequeue(0) // Returns 10
dequeue(1) // Returns 30
Approach 1: Brute Force (Fixed Division)
Intuition
Divide the array into N equal parts, each part dedicated to one queue. Each queue gets S/N slots. Simple but wastes space if queues have unequal usage.
Algorithm
- Divide array into N segments of size S/N
- Each queue i uses indices [i*(S/N), (i+1)*(S/N) - 1]
- Maintain front and rear pointers for each queue
- Handle circular behavior within each segment
java
class NQueues {
private int[] arr;
private int[] front;
private int[] rear;
private int[] count;
private int n; // Number of queues
private int size; // Total array size
private int queueSize; // Size of each queue segment
public NQueues(int numQueues, int totalSize) {
n = numQueues;
size = totalSize;
queueSize = totalSize / numQueues;
arr = new int[size];
front = new int[n];
rear = new int[n];
count = new int[n];
for (int i = 0; i < n; i++) {
front[i] = i * queueSize;
rear[i] = i * queueSize - 1;
count[i] = 0;
}
}
public boolean isFull(int qn) {
return count[qn] == queueSize;
}
public boolean isEmpty(int qn) {
return count[qn] == 0;
}
// O(1)
public boolean enqueue(int x, int qn) {
if (isFull(qn)) {
System.out.println("Queue " + qn + " is full!");
return false;
}
int start = qn * queueSize;
int end = start + queueSize - 1;
// Move rear circularly within the segment
if (rear[qn] < start || rear[qn] >= end) {
rear[qn] = start;
} else {
rear[qn]++;
}
arr[rear[qn]] = x;
count[qn]++;
return true;
}
// O(1)
public int dequeue(int qn) {
if (isEmpty(qn)) {
System.out.println("Queue " + qn + " is empty!");
return -1;
}
int start = qn * queueSize;
int end = start + queueSize - 1;
int x = arr[front[qn]];
// Move front circularly within the segment
if (front[qn] >= end) {
front[qn] = start;
} else {
front[qn]++;
}
count[qn]--;
return x;
}
public static void main(String[] args) {
NQueues nq = new NQueues(3, 9);
nq.enqueue(10, 0);
nq.enqueue(20, 0);
nq.enqueue(30, 1);
nq.enqueue(40, 2);
System.out.println("Dequeue from queue 0: " + nq.dequeue(0)); // 10
System.out.println("Dequeue from queue 1: " + nq.dequeue(1)); // 30
}
}Complexity Analysis
- Time Complexity: O(1) for enqueue and dequeue
- Space Complexity: O(n) for the array, but inefficient space utilization
Approach 2: Optimal (Free List / Linked Indices)
Intuition
Use a free list to track available slots. Each slot points to the next slot in the same queue or to the next free slot. This allows dynamic allocation of space among queues without fixed division.
Algorithm
- Maintain arrays:
arr[]: Stores actual elementsnext[]: Points to next index in same queue (or next free slot)front[]: Front index for each queuerear[]: Rear index for each queue
- Maintain a
freeIndexpointing to the first free slot - On enqueue: Get slot from free list, link it to the queue
- On dequeue: Return slot to free list
java
class NQueues {
private int[] arr; // Array to store elements
private int[] next; // Next index in queue or next free slot
private int[] front; // Front index for each queue
private int[] rear; // Rear index for each queue
private int freeIndex; // Index of first free slot
private int n; // Number of queues
private int size; // Total array size
public NQueues(int numQueues, int totalSize) {
n = numQueues;
size = totalSize;
arr = new int[size];
next = new int[size];
front = new int[n];
rear = new int[n];
// Initialize all queues as empty
for (int i = 0; i < n; i++) {
front[i] = -1;
rear[i] = -1;
}
// Initialize free list
freeIndex = 0;
for (int i = 0; i < size - 1; i++) {
next[i] = i + 1;
}
next[size - 1] = -1;
}
public boolean isFull() {
return freeIndex == -1;
}
public boolean isEmpty(int qn) {
return front[qn] == -1;
}
// O(1)
public boolean enqueue(int x, int qn) {
if (isFull()) {
System.out.println("All queues are full!");
return false;
}
// Get free slot
int slot = freeIndex;
freeIndex = next[slot];
// Store element
arr[slot] = x;
next[slot] = -1;
// Link to queue
if (isEmpty(qn)) {
front[qn] = slot;
} else {
next[rear[qn]] = slot;
}
rear[qn] = slot;
return true;
}
// O(1)
public int dequeue(int qn) {
if (isEmpty(qn)) {
System.out.println("Queue " + qn + " is empty!");
return -1;
}
// Get front slot
int slot = front[qn];
int x = arr[slot];
// Update front
front[qn] = next[slot];
if (front[qn] == -1) {
rear[qn] = -1;
}
// Return slot to free list
next[slot] = freeIndex;
freeIndex = slot;
return x;
}
public static void main(String[] args) {
NQueues nq = new NQueues(3, 6);
nq.enqueue(10, 0);
nq.enqueue(20, 0);
nq.enqueue(30, 1);
nq.enqueue(40, 1);
nq.enqueue(50, 2);
nq.enqueue(60, 0);
nq.enqueue(70, 2); // Should fail
System.out.println("Dequeue from queue 0: " + nq.dequeue(0)); // 10
System.out.println("Dequeue from queue 1: " + nq.dequeue(1)); // 30
System.out.println("Dequeue from queue 0: " + nq.dequeue(0)); // 20
System.out.println("Dequeue from queue 2: " + nq.dequeue(2)); // 50
}
}Complexity Analysis
- Time Complexity: O(1) for all operations
- Space Complexity: O(n) - efficient space utilization
Key Takeaways
- Fixed vs Dynamic: Fixed division wastes space; dynamic allocation with free list is optimal
- Free List: Linked list of available slots enables O(1) allocation/deallocation
- Next Array: Dual purpose - links queue elements and free slots
- Space Efficiency: All queues share the total space dynamically
- Similar to N Stacks: Same technique applies to implementing N stacks in an array
- Real-world use: Memory management, multi-queue task scheduling