Also known as circular buffer, the circular queue is a data structure with a First In First Out access policy, it can be used in several different applications, for example:

  • Message passing buffering
  • Multimedia streaming

It can  be implemented using arrays or linked lists. The choice between the two implementations depends on your requirements, if you need a short and fixed size queue you should use arrays, if you need a longer or variable size queue you should use linked lists with dinamic memory allocation. In both the cases the implementation is very simple. Now we are going to write an implementation using arrays.


Let's start with some theory and definitions:

The queue will store a maximum of MAX_ITEMS items, if we'll try to put more items than MAX_ITEMS, the new items will be lost. To access the queue we will have 5 functions:

  • initialize
  • getItem
  • putItem
  • printQueue
  • isEmpty

The initialize function clears the queue structure and it puts to zero both rear and front pointers

The getItem function retrieves the next available item, the it moves the front pointer ahead by one element

The putItem function puts a new item at the end of the queue and then it moves the rear pointer ahead by one element

The printQueue function prints all valid data in the queue (not all data) valid data are those between front and rear pointers

The isEmpty function returns true if rear and front pointers have the same values.

Here you are the structure:

#define MAX_ITEMS    10
typedef struct circularQueue_s
{
    int     first;
    int     last;
    int     validItems;
    int     data[MAX_ITEMS];
} circularQueue_t;

and the prototypes of the functions:

void initializeQueue(circularQueue_t *theQueue);

int isEmpty(circularQueue_t *theQueue);

int putItem(circularQueue_t *theQueue, int theItemValue);

int getItem(circularQueue_t *theQueue, int *theItemValue);

void printQueue(circularQueue_t *theQueue);

Now let's start coding the functions, the initializeQueue function, simply, sets to zero the structure:

void initializeQueue(circularQueue_t *theQueue)
{
    int i;
    theQueue->validItems  =  0;
    theQueue->first       =  0;
    theQueue->last        =  0;
    for(i=0; i<MAX_ITEMS; i++)
    {
        theQueue->data[i] = 0;
    }        
    return;
}

The isEmpty function verifies if the queue is empty (1) or if it contains some elements (0)

int isEmpty(circularQueue_t *theQueue)
{
    if(theQueue->validItems==0)
        return(1);
    else
        return(0);
}

The putItem function, verifies if there is space in the queue, and, in this case, add an item at the end of the queue (theQueue->last element). Then it updates the value of theQueue->last the modulus operator is needed to stay into the boundaries of the array.

int putItem(circularQueue_t *theQueue, int theItemValue)
{
    if(theQueue->validItems>=MAX_ITEMS)
    {
        printf("The queue is full\n");
        printf("You cannot add items\n");
        return(-1);
    }
    else
    {
        theQueue->validItems++;
        theQueue->data[theQueue->last] = theItemValue;
        theQueue->last = (theQueue->last+1)%MAX_ITEMS;
    }
}

The getItem function returns -1 if the queue is empty, otherwise it takes the first element into the queue, then it updates the number of items and the first element of the queue (look at modulus operator).

int getItem(circularQueue_t *theQueue, int *theItemValue)
{
    if(isEmpty(theQueue))
    {
        printf("isempty\n");
        return(-1);
    }
    else
    {
        *theItemValue=theQueue->data[theQueue->first];
        theQueue->first=(theQueue->first+1)%MAX_ITEMS;
        theQueue->validItems--;
        return(0);
    }
}

The printQueue functions, simply, prints validItems elements of theQueue starting from the theQueue->first element.

void printQueue(circularQueue_t *theQueue)
{
    int aux, aux1;
    aux  = theQueue->first;
    aux1 = theQueue->validItems;
    while(aux1>0)
    {
        printf("Element #%d = %d\n", aux, theQueue->data[aux]);
        aux=(aux+1)%MAX_ITEMS;
        aux1--;
    }
    return;
}

Now let’s write some code to test the implementation,
First of all, the program initializes the structure, then it adds MAX_ITEMS+1 items to the queue, the last item cannot be added to the queue so we shall see a message (“the queue is full”).
The program prints the queue content.

Then the program will get MAX_ITEMS/2 items from the queue.

The program prints the queue content. And as output we should see MAX_ITEMS/2 prints.

int main(void)
{
    int i;
    int readValue;
    circularQueue_t   myQueue;
    
    initializeQueue(&myQueue);
    for(i=0; i<MAX_ITEMS+1; i++)
    {
        putItem(&myQueue, i);
    }
    printQueue(&myQueue);
    
    for(i=0; i<MAX_ITEMS/2; i++)
    {
        getItem(&myQueue, &readValue);
        printf("readValue = %d\n", readValue);
    }
    printQueue(&myQueue);
    exit(EXIT_SUCCESS);
}


Compile the code and try running it.

Gg1

If you’ve found useful this post, please, make a visit to my linkedin profile gg1 to help me growing my ranking.