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.
In printQueue(), line 10…what is aux1–;
In getItem(), line 12…what is theQueue->validItems–;
There seems to be a hyphen in both.
You’re right.
Just modified, thank you.
bonjour,
merci pour votre code, je voudrais savoir comment je peux supprimer a fur et a mesure les elements anciens qui passe dans le buffer svp
merci davance pour vos reposnes
One of the best and simplest Circular Queue Implementation.