A circular queue is a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don't have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.
A circular queue consists of an array that contains the items in the queue, two array indexes and an optional length. The indexes are called the head and tail pointers and are labelled H and T on the diagram.
The head pointer points to the first element in the queue, and the tail pointer points just beyond the last element in the queue. If the tail pointer is before the head pointer, the queue wraps around the end of the array.
There is a problem with this: Both an empty queue and a full queue would be indicated by having the head and tail point to the same element. There are two ways around this: either maintain a variable with the number of items in the queue, or create the array with one more element that you will actually need so that the queue is never full.
Insertion and deletion are very simple. To insert, write the element to the
tail index and increment the tail, wrapping if necessary. To delete, save
the head element and increment the head, wrapping if necessary. Don't use a
modulus operator for wrapping (mod in Pascal, % in
C) as this is very slow. Either use an if statement or (even
better) make the size of the array a power of two and simulate the
mod with a binary and (& in C).
Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).