Queue • Advanced Architecture

K Queues in a Single Array

How do you implement K independent queues using only one underlying array without severe memory fragmentation or O(N) shifting? By using parallel arrays for state management.

The Naive Approach

You could divide the array into K fixed segments. But what if Queue 1 fills its segment while Queue 2's segment is completely empty? You get a "Queue Full" error despite having free space in the array!

The Optimal Strategy

Maintain three arrays: the main `arr` for data, a `front` array of size K storing the head of each queue, a `rear` array of size K for the tails, and a `next` array storing the index of the next free slot (or the next element in the queue).

Free List Management

You manage the empty slots as their own linked list embedded within the `next` array. When you enqueue, you take a slot from the `free` list. When you dequeue, you return the slot to the `free` list. All operations remain O(1).

Loading Lab...

Queue • Advanced Architecture

K Queues in a Single Array

How do you implement K independent queues using only one underlying array without severe memory fragmentation or O(N) shifting? By using parallel arrays for state management.

K Queue One Array

K Queue One Array

K Queues in a Single Array

The Naive Approach

The Optimal Strategy

Free List Management

K Queues in a Single Array

The Naive Approach

The Optimal Strategy

Free List Management