Implement n queue in an array

The problem, simply

You get one array of n boxes. Build k queues inside it, with enqueue(q, x) and dequeue(q) for any queue number q.

The rule: no queue may say "full" while some box anywhere in the array is empty. If one queue is busy and the others are quiet, the busy one should be able to use almost all the boxes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Cut the array into k blocks of n/k boxes. Queue q owns block q and runs as a small circular queue inside it.

1. For queue q, the block starts at start = q * size.
2. Keep head[q] (an offset inside the block) and count[q].
3. Enqueue writes at start + (head[q] + count[q]) % size. Dequeue reads at start + head[q] and moves head[q] forward with % size.

class KQueuesBlocks {
    private final int[] arr, head, count;
    private final int size;                   // boxes per queue

    KQueuesBlocks(int n, int k) {
        arr = new int[n];
        head = new int[k];
        count = new int[k];
        size = n / k;
    }

    boolean enqueue(int q, int x) {
        if (count[q] == size) return false;                  // this block is full
        arr[q * size + (head[q] + count[q]) % size] = x;
        count[q]++;
        return true;
    }

    int dequeue(int q) {
        if (count[q] == 0) throw new RuntimeException("queue " + q + " is empty");
        int x = arr[q * size + head[q]];
        head[q] = (head[q] + 1) % size;
        count[q]--;
        return x;
    }
}

How long it takes: O(1) per action. Extra room: the array plus three numbers per queue, O(n + k). But a queue is full after n/k values even when the rest of the array is empty.

Way 2: the clever way

Turn every box into a link in a chain, using an extra array next.

• arr[i]: the value in box i.
• next[i]: for a used box, the box behind it in the same queue, or -1 if it is the last one. For an empty box, the next empty box.
• front[q] and rear[q]: the first and last box of queue q, or -1 if empty.
• free: the first empty box. At the start the empty chain is 0, 1, 2, ....

1. enqueue(q, x): if free == -1, overflow. Take i = free, move free = next[i]. Write arr[i] = x and next[i] = -1. If queue q is empty, front[q] = i; otherwise hook it on with next[rear[q]] = i. Then rear[q] = i.
2. dequeue(q): if front[q] == -1, it is empty. Take i = front[q] and x = arr[i]. Move front[q] = next[i]; if that is -1, also set rear[q] = -1. Give box i back: next[i] = free, free = i. Return x.

Each queue is a linked list living inside the array, and the empty boxes are one more list.

class KQueues {
    private final int[] arr, next, front, rear;
    private int free;                          // first empty box, -1 if none

    KQueues(int n, int k) {
        arr = new int[n];
        next = new int[n];
        front = new int[k];
        rear = new int[k];
        Arrays.fill(front, -1);
        Arrays.fill(rear, -1);
        for (int i = 0; i < n - 1; i++) next[i] = i + 1;   // chain the empty boxes
        next[n - 1] = -1;
        free = 0;
    }

    boolean enqueue(int q, int x) {
        if (free == -1) return false;          // every box is used
        int i = free;
        free = next[i];                        // take box i off the empty chain
        arr[i] = x;
        next[i] = -1;                          // nobody behind it yet
        if (front[q] == -1) front[q] = i;      // first in an empty queue
        else next[rear[q]] = i;                // hook on behind the old rear
        rear[q] = i;
        return true;
    }

    int dequeue(int q) {
        if (front[q] == -1) throw new RuntimeException("queue " + q + " is empty");
        int i = front[q];
        int x = arr[i];
        front[q] = next[i];                    // the one behind moves up
        if (front[q] == -1) rear[q] = -1;      // queue is empty now
        next[i] = free;                        // box i goes back on the empty chain
        free = i;
        return x;
    }

    boolean isEmpty(int q) { return front[q] == -1; }

    boolean isFull() { return free == -1; }
}

How long it takes: every action changes a handful of numbers, O(1). Extra room: arr and next of size n, and front and rear of size k, so O(n + k).

Watch out for

• In dequeue, read next[i] into front[q] before you overwrite next[i] with free.
• When a queue becomes empty, reset rear[q] too. Otherwise the next enqueue hooks onto a box that now belongs to the empty chain.
• In enqueue, read free = next[i] before changing next[i].
• An empty queue is front[q] == -1. Do not use rear[q] for that unless you keep both in sync.

What interviewers ask next

• How is this different from k stacks in one array? Stacks add and remove at the same end, so they need only top[s]. Queues add at the rear and remove at the front, so they need both front[q] and rear[q].
• Can you add size(q) in O(1)? Keep a count[q] array and update it in both actions.
• Why do this instead of k linked lists? Real linked lists allocate memory for every node. Here all memory is one block made up front, which suits embedded systems and memory pools.
• Can one queue be given a guaranteed minimum? Reserve m boxes per queue up front, and share the rest through the free chain.

Remember this

Grown-up words: the seat cards are the next array (an index based linked list), the usher's chain of empty seats is a free list, front[q] and rear[q] are the head and tail of queue q, and the fixed blocks in Way 1 are a static partition.