tough programming problem

[[dx/x]=HUNT3R]

I'm working on a solution to this problem for possible employment with a computer game company. Just thought I would post it and see if anyone had any different ideas on how to implement a solution. The problem is to write a set of functions to manage a variable number of byte queues, each with variable length, in a small, fixed amount of memory. You should provide implementations of the following four functions:
Q createQ(); Creates a FIFO byte queue, returning a handle to the created queue.

void destroyQ(Q q); Destroy an earlier created byte queue.
void enQ(Q q, unsigned char b); Adds a new byte to a queue.
unsigned char deQ(Q q); Pops the next byte off the FIFO queue.

So, the output from the following set of calls:

Q q0 = createQ();
enQ(q0, 0);
enQ(q0, 1);
Q q1 = createQ();
enQ(q1, 3);
enQ(q0, 2);
enQ(q1, 4);
printf("%d %d\n", deQ(q0), deQ(q0));
enQ(q0, 5);
enQ(q1, 6)
printf("%d %d\n", deQ(q0), deQ(q0));
destroyQ(q0);
printf("%d %d %d\n" , deQ(q1), deQ(q1), deQ(q1));
destroyQ(q1);

should be:

0 1
2 5
3 4 6

You can define the type Q to be whatever you want.

Your code is not allowed to call malloc() or other heap management routines. Instead, all storage (other than local variables in your functions) should be done in a provided array:

unsigned char data[2048];
Memory efficiency is important. On average while your system is running, there will be a dozen or so queues with an average of 100 or so bytes in each queue. Your functions may be asked to create a larger number of queues with less bytes in each. Your functions may be asked to create a smaller number of queues with more bytes in each.

If you are unable to satisfy a request due to lack of memory, your code should call a provided failure function, which will not return:

void onOutOfMemory();
If the caller makes an illegal request, like attempting to deQ a byte from an empty queue, your code should call a provided failure function, which will not return:

void onIllegalOperation();
Worst-case performance when adding and removing bytes is important.

There may be spikes in the number of queues allocated, or in the size of an individual queue. Your code should not assume a maximum number of bytes in a queue (other than that imposed by the total amount of memory available, of course!) You can assume that no more than 64 queues will be created at once.

I'm thinking that I'm going to have to waste 2 bytes at the beginning of each queue to record it's length. Then keep all queues at the beginning of memory (the 2048 array) as they are created so that memory will not become fragmented once a lot of queues are created. The problem with that is that all queues will have to be adjusted in memory every time just one queue is enq'd or deq'd. Thats like a defrag with every enq or deq which will be very slow and time consuming. But one can't assume that all queues will have a common size. I also thought about sectioning the memory off into 64 32-bit queues and letting a queue run over into it's neighbor's space if it has to. But it is possible that the user may create 1 2000-element queue and then 48 1-element queues. I'm not looking for someone to write the code for me, I'm just asking around for ideas better than mine... any takers?