Because of time and space constraints, a circular queue will be implemented as an array with indexes head
and tail, pointing, respectively, to the delete end and insert end of the queue.
Such a queue is normally implemented with the tail pointing to the next available place. Wrap-around is used
to make efficient use of allocated space.
If the queue is a power of two, we can implement wrap around using the & operator. This is good because
& is much faster than %.
When x is a power of 2, x % k is equivalent to x & (k-1).
Suppose the array is a power of 2, for example, 4. Take any int x value that may need to be
wrapped around.
x x%4 x & 0x03
0 0 0x00 & 0x03 => 0x00 = 0
1 1 0x01 & 0x03 => 0x01 = 1
2 2 0x02 & 0x03 => 2
3 3 0x03 & 0x03 => 3
4 0 0x04 & 0x03 => 0
5 1 0x05 & 0x03 => 1
6 2 0x06 & 0x03 => 2
... ... ...
Because of the wrap-around, we are in danger of confusing an empty queue with a full queue. To fix that problem, we have to either know the length of the array, or we have to keep track of the current size of the queue.
For subsequent discussion, I'm assuming we're programming in
C or another low-level language with minimal compiler-supplied support for
array processing.
Also, I'm going to organize the code into functions -- but in the
microprocessor "world", use macros or other inline code; when possible, avoid functions for heavily used code,
use macros instead.
size which we increment on an insert and decrement on a delete.
int[QS] myQueue; // QS is a power of 2
Initialize the queue with
head = 0; tail = 0;
Insert at tail, delete from head.
The maximum number of elements in the queue is QS - 1 (i.e., a full queue has one fewer
element than QS). This is to distinguish between full queue and empty queue.
The test for the empty queue is :
int isEmpty() {
if (head == tail) return 1;
else return 0;
} QS is the allocated length of the array):
int isFull() {
if (head == ( (t+1) & (QS-1) ) // i.e., (head == (tail+1) % QS )
return 1;
} For this implementation (maximum queue size is one less than QS, the actual array length), the insert and
delete functions are:
void addElement() {
if (!isFull()) {
myQueue[tail] = value;
tail = (tail + 1) & (QS-1); // though it's bad form to recompute QS-1 repeatedly!
}
else error("insert failure");
}
int delElement(){
if (!isEmpty() ) {
int val = myQueue[head];
head = (head+1) & (QS-1);
return value;
}
else error("delete failure");
}