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:
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:
and the prototypes of the functions:
Now let's start coding the functions, the initializeQueue function, simply, sets to zero the structure:
The isEmpty function verifies if the queue is empty (1) or if it contains some elements (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.
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).
The printQueue functions, simply, prints validItems elements of theQueue starting from the theQueue->first element.
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.
Compile the code and try running it.
If you’ve found useful this post, please, make a visit to my linkedin profile gg1 to help me growing my ranking.