ECEN 390 - Laser Tag Project

Let's look at a a few simple examples of how an array can be used to implement a circular buffer, using the queue_t data structure that I provide below. First, to keep things simple, let's make our queue big enough to hold 3 elements (3 elements of type double, in our case). Using the code that I provided below, you would say the following:

#include "queue.h"
queue_t myQueue;
queue_init(&myQueue, 4);

One thing to note in the code above is that we pass the address of myQueue to queue_init. We do this for the sake of efficiency in 'C', and this is because this is what the queue_init() code expects. Once we execute the code above, a pictorial view of myQueue would look something like right after queue_init() has been called) is shown below. Note that enough memory for 5 doubles has been allocated. But, as I said before, this queue can only hold 4 doubles.

This queue, is by definition, empty because indexIn and indexOut are the same value (0, in this case). Now, let's look at what the queue looks like after we have “pushed” 4 values (23.4, 3,14, 72.1, 89.4).

Even though there appears to be one empty location in the queue (location 4), the queue is now considered to be full. Why is this so? Because indexIn always points to the empty location where the next “push” will store data. If we were to do another “push” when the queue is in its current state, indexIn would be wrapped around so that is back to 0, and because the queue is considered to be empty anytime indexIn and indexOut are the same value, the queue would become empty. Thus, whenever we “push” a new value onto the queue, the queue needs to do a simple test: if indexIn were incremented, would it be equal to indexOut? If so, the queue is currently full and it is not possible to “push” another value onto the queue.

Now, let's perform two “pops” on our queue, removing two elements. After two “pops”, our queue would be shown pictorially below:

As shown, indexOut has moved up two locations. Now, let's say that we want to “push” two new values onto our queue. When “pushing” a new value, the queue would need to check if it is full. It is not because, if indexIn is incremented and wraps around to location 0, it will not be equal to indexOut because indexOut now has the value of 2.

Now, let's look at the queue after “pushing” two new values (51.5 and 49.2).

indexIn now has the value of 1 and you can see that two values have been “pushed” onto the queue. Is our queue full? It must be, because the queue can only hold 4 elements. Our “empty” location is location 1 (currently showing 3.14 but remember that value was previously “popped” off). Let's try the “full test”. If we were to increment indexIn it would have the same value as indexOut, so the queue is currently full.

Carefully study the example above so you can see how the circular buffer works with an array, and also so you can see why there is always an empty location in the queue when implemented this way.

Why the extra location? In the queue.c code that I provided you will note that I allocate one additional memory location. My presumption is that you will implement the queue as a circular buffer that uses an empty location to deal with the empty/full problem. Please see this web page on circular buffers as it explains this issue. You are not required to implement the queue using a circular buffer. However, it is usually about the easiest thing to debug and get running.