Comments on, and pseudocode for, circular queues for programming a microprocessor - Draft 1.1

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.

We know the length of the array, because we allocated that much space for the array. In order to know the current size of the queue, we would have to maintain a variable 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;
   }  

The test for the full queue is (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");
    }
    


Reference:








This paper, even in this draft edition, must be properly cited if you make any use of it.
Date: 15 December 2006
Prepared for COSC 422, FALL 2006