Updated April 7, 2023
Definition of Circular Queue in C
C Circular queue is defined as an implementation of the concept of the circular queue in C programming language in a practical manner. Circular Queue is coined from the concept of a linear data structure that allows operations to be performed on the structure as FIFO (First In First Out) principle and the last position being connected to the first position to make the linear structure as a circular one and this implementation is also known as a ring buffer. The implementation of a circular queue solves the limitations of a normal queue, i.e. to have a possibility of storing values even if the queue reaches the end but the queue in itself has some void spaces within it due to empty spaces at the front as FIFO technique is implemented.
Syntax
In the syntax section, we will go through some syntaxes which are required for the implementation of the circular queue in C. The elements in this section of the article on circular queue don’t necessarily depict the entire runnable code, but gives a sense of what are the different placeholders that are in place for the queue methodology to be able to execute successfully.
Declaring the header in C:
#include<stdio.h>If statement in C:
if ( <variable name> <condition operator> <check value)> ){
<Statements>;
}
else{
<Statements>;
}Function definition in C:
<return type> <function name>(){
<Function statements>;
}Printing of statements in C:
printf(" <Statements to be printed> " );How Circular queue works in C?
By now we pretty much have a fair idea of the structure of the circular queue, and it implements FIFO ordering. What FIFO essentially means is elements that go in first are removed the first. This structure is similar to a queue at an airport, wherein the person standing at the first gets to board the flight and so on till the last passenger boards the flight. But now what we talked about a queue at the airport, is like a linear queue. There is a limited number of seats in a flight and hence as the capacity gets full no one is allowed to be a part of the line or in other words doesn’t even get the ticket. Now assume a similar case where we have limited resources in a computer, and one is performing memory-intensive tasks all of which takes some time. Now the task which starts first followed by tasks that subsequently start coming consecutively starts getting piled up and now if the resource gets full, the other task is out into the waitlist. Assume that had the scenario been like the one we talked about in flights, any task in the waitlist will never execute as the line has completely ended. Now let us say we link the last element to the first element saying that if the last element is filled check if the first element is free and if yes, then start putting or inserting the task in resource management and keep the workflow continuous.
With the same intention circular queue works in C. This methodology is known as circular increment where one tries to keep incrementing the counter or the pointer that points to the tail of the array in case of entering any new element (This process is known as enqueuing) and increasing the pointer that points to the head of the array when any element is removed (This process is known as dequeuing). Apart from the elements we just talked about i.e. enqueuing, dequeuing, front (pointer), rear (pointer) we also have an operation isEmpty or isFull which does a check on the queue to understand if the queue is empty or full.
The circular increment is performed by modulo division, which gives the remainder of the division we perform by the corresponding numerator and denominator. Now to understand the working of modulo division, in case of enqueuing, the rear pointer is incremented by ( rear + 1 )%( N ) where N is array length. In the case of dequeuing, the front pointer is also incremented by ( front + 1 )%( N ). This happens because let us say that the rear pointer is at the end of the array, hence the index number is N-1, and now if the index is incremented, it will reach N, which is like an out-of-bound scenario. Thus, we resort to ( rear + 1 )%( N ) so that when rear is replaced by N-1, we get ((N-1)+1)%N = N%N = 0. Thus the rear now again starts pointing to the start only on the condition that the queue is notFull. In case the queue is full one can easily throw out an exception saying that the queue is full and can’t be loaded with more data. Let us now go through the process of enqueue and dequeue as pseudocode so that when we go through the code, it be super simple to grasp, and also the working of a circular queue is clearer.
Enqueue:
- Check if the Queue is full. If yes, throw an exception that nothing can be enqueued.
- The first element should contain FRONT as 0.
- Using modulo division increment the REAR index.
- Add the element to the new REAR index.
Dequeue:
- Check if the queue is empty. If yes, throw an exception that nothing can be dequeued.
- The value pointed by FRONT is returned.
- Using modulo division increment the FRONT index.
- In case of last element, we can forcefully set values of FRONT and REAR to -1.
Examples
Let us discuss examples of
Example #1
Implementation of circular Queue:
Syntax:
#include <stdio.h>
#define ARRSIZE 6
int array[ARRSIZE];
int front = -1, rear = -1;
// Is the queue full?
int checkFull() {
if ((front == rear + 1) || (front == 0 && rear == ARRSIZE - 1)) return 1;
return 0;
}
// Is the Queue Empty?
int checkEmpty() {
if (front == -1) return 1;
return 0;
}
// Element Adding
void enQueue(int ele) {
if (checkFull())
printf("\n Can't enter more. Queue Full \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % ARRSIZE;
array[rear] = ele;
printf("\n Pushed -> %d", ele);
}
}
// Element removing
int deQueue() {
int ele;
if (checkEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
ele = array[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Reset Queue after all elements are removed
else {
front = (front + 1) % ARRSIZE;
}
printf("\n Popped out -> %d \n", ele);
return (ele);
}
}
// Queue Display
void display() {
int i;
if (checkEmpty())
printf(" \n The queue is Empty\n");
else {
printf("\n Pointer for first element -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % ARRSIZE) {
printf("%d ", array[i]);
}
printf("%d ", array[i]);
printf("\n Pointer for Last element -> %d \n", rear);
}
}
int main() {
// Will print out an empty array
deQueue();
enQueue(10);
enQueue(15);
enQueue(20);
enQueue(30);
enQueue(50);
enQueue(60);
// Will Fail inserting as the Queue is Full
enQueue(1);
display();
deQueue();
display();
// Will succeed as we removed one element using deQueue()
enQueue(2);
display();
// Will again Fail inserting as the Queue is Full
enQueue(100);
return 0;
}Output:
Conclusion
To conclude, in this article we have learned the working of the circular queue in C. Next, we encourage readers to try out switch case which will be a more user-friendly implementation of the circular queue as the entire flexibility will be on the user for pushing and popping of elements.
Recommended Articles
This is a guide to Circular Queue in C. Here we discuss definition, syntax, How Circular queue works in C? examples with code implementation. You may also have a look at the following articles to learn more –
