Expert: Zlatko - 11/25/2009

Question
how to implement 2 queues in a single array?  

Answer
Hello Santosh

First simplify your problem to 1 queue in an array. For your array, you have a beginning at 0 and an end at some array index. Lets call it END. For a queue you have a head, and a tail. Each is an index into the array. In a queue, items are added at the tail, and removed from the head.

Now you have a design choice. You can implement your queue so that when an item is removed at the head, all the other items are shifted in memory so that the head is always at the start of the array. I don't like that method because all the moving is just naive. I prefer the implementation where the head moves as items are taken off the queue. Of course, you can imagine as the head, and tail are moving, they will eventually go past the end of the array and we cannot have that. Basically once the head or tail go past the end of the array (END), they must wrap around to the start of the array (0)

We must have our definitions straight.

The first available spot in the array is at 0
The last available spot is at END
A spot in the array either has an item, or is empty.
The head points to the first item on the queue, if the queue has any items.
The tail points to the first empty spot on the queue, if an empty spot exists.
When I say points, I don't mean it is a pointer. It is an index into the array.
A queue is empty if Head and Tail are the same.
A queue is full if incrementing Tail would cause it to be the same as the Head.

With these definitions, one spot on the array will be empty when the queue is full. An alternative is to have a counter for the number of elements on the queue. Then you can use the counter to determine if the queue is full or empty or maybe you can change the definitions in some other way so that you can use all the spots on the array. Think about it.

Now that we have our definitions straight. We can initialize the queue to be empty.

head = 0;
tail = 0;

We need functions to insert and remove

function insert(item)
{
   if queue is not full
   {
       queue[tail] = item
       tail = advance(tail);
   }
}

function remove()
{
   if queue is not empty
   {
       item = queue[head];
       head = advance(head);
       return item;
   }
}

Now we need a function which will advance an index, and wrap it around to the start of the array.

function advance(int index)
{
   newIndex = index + 1;
   if (newIndex > END) newIndex = 0;
   return newIndex;
}

And we need functions to tell if a queue is empty or full, based on our definitions

function isEmpty()
{
   if (head == tail) return true;
   else return false;
}

function isFull()
{
   newIndex = advance(tail);
   if (newIndex == head) return true;
   else return false;
}

I don't really understand why you would want 2 queues on a single array, and I'm not sure I understand the question. But, I guess that two queues on a single array is similar, but now you cannot assume that a queue starts at Index 0, so you need a BEGIN variable as well as an END. You would need separate BEGIN/END variables for each queue.

Now it's your turn to try an implementation. Let me know how you do.

Best regards
Zlatko