How to efficiently implement k Queues in a single array?

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

public class KQueues {
    int k, n;
    int[] arr; // Array of size n to store actual content to be stored in queues
    int[] front; // Stores front index of queues
    int[] rear; // Stores rear index of queues
    int[] next; // next[i] will store the next free space if you want to occupy this space in
                // original array otherwise it something already is present at this index, then
                // it will store the index of next element in the queue OR -1 if it
                // is the last element itself
    int free; // To store the first free space index

    KQueues(int k, int n) {
        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; // Last index has no free space after it

    }

    // To enqueue an item in queue number 'i' where i is from 0 to k-1
    private void enqueue(int item, int i) {
        // If no free space is available
        if (free == -1) {
            System.out.println("queue overflow");
            return;
        }
        // Next free slot
        int nextFree = next[free];
        // If this is the first element in the stack
        if (front[i] == -1)
            rear[i] = front[i] = free;
        // Update next of rear and then rear for queue number 'i'
        else {
            next[rear[i]] = free;
            rear[i] = 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) {
        // If the queue is empty
        if (front[i] == -1) {
            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 top of queue
        return arr[frontIndex];
    }
}

Last updated