Sunday, January 21, 2007

Implement a queue using an array...

I have been reviewing some basic data structure lately. The queue is one of the basic data structure, just as other data structure, you can use the array or the link list to implement it.

When using an array to implement the the queue, there are two pointers, one points to the head, and the other points to the end. If we have array of size N to implement an list with N elements. We will have 0<=head<N, and 0<=tail<N, and the difference between head and tail satisfies 0<=(head-tail)mod N <N. There are only n distinct differences, with queue length 0, 1, 2, ... , N-1. But the queue could have N elements too, it means that the number of the enumerations(N+1) of the queue is larger than what the underlying array can offer.

Actually, when the array is empty (the queue has 0 element), the head and the tail points to the same position, and when the array is full, the head and the tail points to the same position too. So, we cannot tell whether the list is empty of full solely based on the head and tail position.

For example, when the queue is just created, the head points to 0 piston, and the tail points to the N-1 position in the array, and when we add the first element, the tail position will move to the first element. If we keep adding 10 elements, then we get to a point the tail position will point to the 10th element again. Then the head and tail position actually points to the exact same position as the empty queue.

There are two options for dealing with this problem. The first is to limit the number of elements in the queue to be at most n-1. The other is to use another member variable , count, to keep tract explicitly of the actual number of elements in the queue rather than to infer the number from the head and tail variables. Both are valid options.

In the first option, we let the tail point to the 0 element, and the head point to the N position. So, if we move the head right, then we'll reach the tail, that's the empty situation. On the other hand, if we have a full queue, we move the tail right, we'll reach the head.

The empty condition is happening when head/N==tail/N. And the full condition is happening tail+1==head.

No comments: