Implement k Queues in a Single Array

JavaView on GFG

Intuition

Implement k queues using a single array efficiently. Use free list and index arrays to track fronts, rears, and next.

Algorithm

1Maintain arrays: front[k], rear[k] (indices in main array), next[n] (next free or next in queue).
2Free list manages unused slots. Enqueue: take from free list, link. Dequeue: return to free list.

Common Pitfalls

•Space-efficient: O(n+k) space for n total elements across k queues. Complex pointer arithmetic.

Implement k Queues in a Single Array.java

Java

// Approach: Use extra 'next' and 'front' arrays for free slots and queue heads. Linked-list-style management.
// Time: O(1) per operation Space: O(n)
import java.util.*;

class kQueues {
    ArrayList<Integer>[] Q;
    int n;
    int currSize;

    kQueues(int n, int k) {

        // member initialization
        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] temp = new ArrayList[k];
        Q = temp;

        this.n = n; // total max size
        currSize = 0; // currently filled with
        for (int i = 0; i < k; i++)
            Q[i] = new ArrayList<>();
    }

    void enqueue(int x, int i) {
        if (currSize == n)
            return; // already full

        Q[i].add(x);
        currSize++; // update size
    }

    int dequeue(int i) {
        if (Q[i].isEmpty())
            return -1; // q is empty

        currSize--;
        return Q[i].remove(0);
    }

    boolean isEmpty(int i) {
        return Q[i].size() == 0;
    }

    boolean isFull() {
        return n == currSize; // curr size == max capacity
    }
}

Was this solution helpful?