FIFO queue can be explained as: what comes first is served first, what comes next have to wait until the first is finished.

But what are we talking about?
In embedded systems very often data is made available from the external world to be handled by the firmware.
Depending from system requirements and capabilities, the data can or, more likely, must be processed as soon as it is acquired.
Other times, especially for certain peripherals, it can be, or must be processed later on, so no fuss no muss!
This is our case.
So the problem usually is: data is coming from an external source, I don't want to lose it, on the other hand, I will process it as soon as my application needs to do it.
The base concept here is "First In First Out" aka FIFO (First In, First Out) like a queue at the post office, where Mr. Smith arrived at 8:00, Mr. Abey at 8:01 and Miss Green at 8:02, at the same front desk. The clerk at the front desk, whose shift begins at 8:05, will first attend Mr. Smith requests then Mr. Abey's and finally Miss Green's. The service order respects the arrival order.
We want to implement this system in our software.
The general idea is to create a memory area for the temporary storage of incoming data and a few functions to write and read data in this area (usually called buffer).
Let's have a look at the following diagram:

We here assume an area of 8 locations (an 8 elements, zero based array called Buffer) without specifing data type.
We also declared three variables : writePosQ, readPosQ, countItemQ, inizializing all of them to zero.
This layout identifies our queue prototype.
At the beginning the queue is empty, and we can testify this status by observing :

1. countItemQ equals zero.
2. writePosQ equals readPosQ.
   

Ok, keep in mind the previous observations, we will make use of them later on.
Now, an external event makes datum "X" available and we want to insert it in the queue, so we use a function called insertDataQueue(), here described step by step :

1. Write "X" in the array element Buffer[writePosQ], since writePosQ equals zero this is equivalent to Buffer[0]="X".
2. Increment writePosQ.
3. Increment countItemQ.

The following diagram shows queue status after the first insertion:

Suppose one more external event makes datum "Y" available, again we want to insert it in the queue:

1. Write "Y" in the array element Buffer[writePosQ], since writePosQ equals 1 this is equivalent to Buffer[1]="Y".
2. Increment writePosQ.
3. Increment countItemQ..

The following diagram shows queue status after the second insertion:

Let's stop here about data insertion, we move to analyze data extraction, but we will come back here, since we left a few open questions.
In the mean while our application wants to know whether incoming data is available or not.
So we can think about a function that returns queue status, let's call it isQueueEmpty.

A few paragraph ago, we noted that a queue is empty when countItemQ equals zero.
So why don't we re write the previous definition in the following way ?

So far so good.
Now we want to extract element from our queue with a function called extractDataQueue() here described step by step:

1. Return the array element Buffer[readPosQ], since readPosQ equals zero this is equivalent to return Buffer[0].
2. Increment readPosQ.
3. Decrement countItemQ.

The following diagram shows queue status after the first extraction:

Since the queue is not still empty (isQueueEmpty() tells us so..), we want to extract one more element from our queue calling again extractDataQueue():
As from the previous explanation:

1. Return the array element Buffer[readPosQ], since readPosQ equals one this is equivalent to return Buffer[1].
2. Increment readPosQ.
3. Decrement countItemQ..

The following diagram shows queue status after the second extraction:

Calling again isQueueEmpty() returns True, so we go on with our business.
It looks quite simple to implement, and we all love simple things....
In the following C source you can find a first step implementation of these functions, assuming our incoming data are chars from a serial port.

//	Set the maximum queue length
#define	MAXQUEUELEN		8
#define	QUEUEMASK		MAXQUEUELEN-1

//	Declare queue variables
int writePosQ=0, readPosQ=0, countItemQ=0;
char Buffer[MAXQUEUELEN];

//	Returns TRUE if queue is empty
int isQueueEmpty()
{
int retval=TRUE;

	if(countItemQ!=0)
	{
		retval=FALSE;
	}
	return retval;

}

//	Inserts a new item in the queue
void insertDataQueue(char d)
{
	//	Check if queue is not full
	if(countItemQ!=MAXQUEUELEN)
	{
		//	There is still room for data
		Buffer[writePosQ]=d;
		//	Move write pointer to next location
		writePosQ++;
		//	Make it circular
		writePosQ&=QUEUEMASK;
		//	On more item inserted, count it.
		countItemQ++;
	}
}

//	Extracts a new item in the queue
//	We here assume we already tested queue status, and found data is available.
//	So no further control is done on queue status.
char extractDataQueue(void)
{
char retval='\0';

	retval=Buffer[readPosQ];
	//	Move write pointer to next location
	readPosQ++;
	//	Make it circular
	readPosQ&=QUEUEMASK;
	//	On more item extracted, count it.
	countItemQ--;
	return retval;
}

Observing the code, we can see we tackled a couple of issues previously left open :

1. Circular Array
2. Buffer Overrun
   

• What should I do when one of the two pointers (writePosQ, readPosQ) reaches the end of the buffer array ?

Simple, we set it back to the beginning of the buffer array. It's like a dog biting its own tail... we call this kind of structure circular array. This is done by the bitwise AND operation (&).
This method is convenient in terms of speed, bitwise AND are fast.
On the other hand it forces the programmer to use as MAXQUEUELEN powers of two (1,2,4,8,16,32,64,128,256,512....), and sometimes available RAM is not that much...
If RAM (and not speed) is the issue then we can use MAXQUEUELEN sizes that are the right balance between RAM cost and system performance. In this case we must rewrite the code in the following way:

	//	Make it circular
	if(readPosQ==MAXQUEUELEN)
	{
		readPosQ=0;	
	}

• What if the estracting process is slower than the inserting one? For this error, called buffer overrun we have two choices :

1. We loose all incoming data exceeding buffer size, existing data in the buffer is not overwritten.
2. We overwrite the last buffer location with the incoming data.
   

Which of the two options should we adopt ?
The first one makes more sense to me (take a look at the code again..), but there could be cases where number two is a better choice.
As a matter of fact if a buffer overrun happens, we should seriously think to go back to the blackboard, and think again about system performance, capabilities and buffer dimensions....

Just a little usage example:

void main(void)
{

	while(1)
	{
		................
		................

		//	Make sure incoming data is available
		if(EXERNALDATAAVAILABLE)
		{
			data=READPORT();
			insertDataQueue(data);
		}

		................
		................



		while(!isQueeueEmpty())
		{
			//	Extract and process data
			mean=extractDataQueue();
			//	Do what you need
			................
			................
			................
			................
		}

	}
}

Though the code is written in C, it can be easily implemented in other high level languages, and test it on your desktop computer.

Anyway, please do note that when I wrote this code I assumed:

• Only one queue is managed in the program. Code is not optimized to handle more queues.
• Access to Buffer is not concurrent, meaning while an extraction is made no insertion is permitted and viceversa. This also means that if you adopt this code as it is in an application using queues in ISR, or in RTOS you are going to smash your face in a very hard wall..

Thinking about it, perhaps next article could focus on these two issues....
In the meanwhile, have fun.