Circular Queue

Explore the utility of circular queues in operating systems, crucial for managing process execution through FIFO principles. Often termed ‘Ring Buffer,’ this data structure efficiently stores processes, ensuring seamless resource allocation. Unlike traditional queues, a circular queue optimizes space by overwriting old entries when full, enabling continuous operation and execution management within computing environments.

Explanation: In the figure above, we see that there is a simple queue(Q) with maximum size,N = 5. The queue pointers- Rear Pointer represented by R and Front Pointer represented by F. Initially, Q is empty and R and F is set to -1. The following tasks are performed on Q:

(i) Insert elements: 4,5,6,3,9. When 4 is inserted, R = 0 and F = 0 (F is incremented in insertion of first element). Next, R is incremented for the rest of the insertions. So, at the end we have F = 0 and R = 4 (or N-1).

(ii) Delete 4,5,6,3. With every deletion F is incremented as follows:So, in this step we end up F = 4 and R = 4. Both of them are pointing to the last element in Q.

(iii) Insert 1: For insertion we need to increment the R pointer but we can clearly see that R is pointing to the end of the Q. We have reached the end of the so R cannot be incremented. The F pointer is also at the end of the Q. This implies that the current size of the Q is 1, that is, it is holding only one element and the rest of the spaces in the Q are empty.

This brings us to this conclusion that in spite of having empty or vacant cells in the Q we cannot insert a new element in such conditions.

What is Circular Queue?

A circular queue is a linear queue that behaves as if the end position of the queue is connected to the start position, forming a circular ring. It is also known as a Ring Buffer. In array-based implementation, the circular behavior is achieved by manipulating the queue pointers. In linked list-based implementation, we will explore it further.

The queue pointers( Front pointer and Rear pointer) will start moving from 0 to N-1 (Maximum size of Queue = N) and after reaching N-1, they come back to 0, again they start from 0,1.., upto N-1 and they continue moving around the Queue round and round.

Let us quickly see how it is achieved in array based implementations. Speaking in the language of Maths, you must have used mod (modular arithmetic) while coding algorithms for solving some maths problems. Mod has the power to restrict any number to a range 0..(N-1) if we operate on mod n. Similar things happen with the indices and pointers movement in a circular queue. We do a mod of indices with N where N is the size of the queue. After N-1 when we increment the index, it becomes N and N %N =0 returns 0 for the next index.

How Circular Queue Works

Let’s take the same example that we used for the simple queue above and see how circular queues overcome the situation when we have some unused spaces left after deletion.
We will insert elements until the circular queue is full. Next, we will try deleting some of them and see if we can insert new elements in the vacated spaces.

Circular Queue Implementation

When you refer to different books, you may find different assumptions and implementations based on them. Here, we are considering the following:

• The queue pointers Front and Rear are initially set to -1. We can consider Front == -1 as a condition to check if the given queue is empty.
• To insert an element we first increase the Rear pointer and then insert the element at the new Rear position.
• When we insert an element in an empty queue, we increase the Front pointer from -1 to 0.
• Single element: If Front==Rear and Front != -1, we can say there is only one element in the queue.
• To delete an element we simply increase the Front pointer. We do not need to delete that element by assigning 0 or garbage value. We assume that the positions which do not fall between Front and Rear pointers hold garbage value and so they are empty.
• To find the occupied space or the number of elements present in the queue:
  • If Rear >= Front, no_of_elements_present = Rear - Front + 1; as the number of elements in a range is its upper limit – its lower limit + 1. In the figure below, the maximum size of the circular queue, n = 7. The rear pointer, R points to index 4 and the front pointer, F points to index 1. Since R > F, the number of elements thus present = R - F + 1 = 4 - 1 + 1 = 4.
    
    

• If Front > Rear, then no_of_elements_present = N(max-size) - (Front - Rear - 1). As shown in the image below, we subtract the empty spaces (Front - Rear - 1) from the total space, N to get the occupied space or number of elements in the queue. In the figure below, the maximum size of the circular queue, n = 7. The rear pointer, R points to index 1 and the front pointer, F points to index 3. Since R < F, the number of elements thus present = n - (R - F) + 1 = 7 - ( 3 - 1) + 1 = 6.

Operations

Let us now see the four basic operations performed by a circular queue.
(Please note: N = maximum size of the queue, F = front pointer, R = Rear pointer, Q = Circular Queue)

1. front(): This function returns the front element, that is the element pointed by the front pointer, from the circular queue.
   Return Q[F]
2. rear(): This function returns the rear element, that is the element pointed by the rear pointer, from the circular queue.
   Return Q[R]
3. enQueue(value): This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at the rear position according to the FIFO principle.
4. deQueue(): This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from the front position according to FIFO principle.

Enqueue Operation

As discussed above in Enqueue Operation [Insertion in Q] we will have the following steps:

Step 1: Check Overflow Condition. Overflow will arise when the circular queue is full and we try to insert a new element. This happens when the position/index where the new element is to be inserted [(Rear + 1)th position] is the start position, ie., the position with the first element pointed by the front pointer. We cannot insert an element in such a condition and exit with an overflow message.

If (Rear + 1) % N == Front
Print ” Overflow ” and Exit

Step 2: Check if Q is Empty and Set Rear
If Front == -1 and Rear == -1
Set Front = Rear = 0
Else
Set Rear = (Rear + 1) % N

Step 3: Insert the new element
Set Q[Rear] = Element_to_Insert

Step 4: Return
Exit

Dequeue Operation

Let’s see the steps for Dequeue Operation [ Deletion from Q]

Step 1: Check Underflow Condition

If Front == -1
Print ” Underflow ” and Exit

Step 2: Retrieve the front element

Set Deleted_Element = Q[Front]

Step 3: Check if Q has only 1 element left

If Front == REAR
Set Front = Rear = -1
Else
Set Front =( Front + 1) % N

Step 4: Return the Deleted Element

Return Deleted_Element and Exit

Application of Circular Queue

1. Memory Management in Operating System: In operating systems, processes are stored in a circular process queue wherein the old processes are removed for execution and new processes are added or queued. The unused memory locations post process dequeue are utilized using circular queues which would have not been possible in ordinary queues.
2. Traffic system: In computer controlled traffic systems, circular queues are used to switch on the traffic lights one by one repeatedly as per the time set.
3. CPU Scheduling: Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

Implementation of circular queue using Array

Circular queues can be implemented using arrays of fixed size. To enqueue an element, we check if the queue is full and exit if so. If the queue is empty, we set the front pointer to the index of the first element. Then, we increment the rear pointer and insert the new element. For dequeue, if the queue is empty, we exit. Otherwise, we fetch the rear element and store it. If it’s the last element, we set the pointers to -1; otherwise, we increment the front pointer and return the stored element.Following is the implementation code:

/* Implementation of circular queue using array in C */

#include<stdio.h>
#include<stdlib.h>
# define N 5  //N = Maximum Size of the Q 
int cq[N];   //cq = Circular Queue
int front=-1;  
int rear=-1; 

void enqueue(int item);
int dequeue();
int isEmpty();
int isFull();

void enqueue(int item)  
{  
    if(isFull())  
    {  
        printf("Queue Overflow\n");
        exit(1);
    }
    if(front == -1){
        front=0;  
    }  
    rear=(rear+1)%N;       // rear is incremented  
    cq[rear]=item;     // assigning a value to the queue at the rear position.  
} 

int dequeue()  
{  
    int deleted_item;
    if(isEmpty()) 
    {  
        printf("Queue Underflow\n");  
        exit(1);         // To show Failure Exit. 
    }  
    deleted_item = cq[front];
    if(front==rear)  // cq has only 1 element
    { 
       front=-1;  
       rear=-1;  
    }   
    else  
    {  
       front = (front + 1)%N;
    }  

    return deleted_item;
}  

int isEmpty(){
    return ( (front == -1) ? 1 : 0); 
}

int isFull(){
    return ( ( (rear + 1)%N == front) ? 1 : 0); 
}

void display()  
{  
    int i;
    if(isEmpty())  
    {  
        printf("Queue Underflow\n.");  
    return;
    }  
   i = front;
        if(front < rear){
            while(i<=rear)  
            {  
                printf("%d,", cq[i]);  
                i=i+1;  
            }
        }
        else{
            while(i != rear)  
            {  
                printf("%d,", cq[i]);  
                i=(i+1)%N;  
            }
            printf("%d,", cq[i]);
        }

}  

int main()  
{
    // Insert elements : 42, 66, 35, 59, 17
    enqueue(42);
    enqueue(66);
    enqueue(35);
    enqueue(59);
    enqueue(17);
    display();
    // Delete first 2 elements
    printf("Deleted Element is: %d\n",dequeue());
    printf("Deleted Element is: %d\n",dequeue());
    display();
    // Insert 10
    enqueue(10);
    display();
    return 0;  
} 

Output:

Elements in the Queue are : 42,66,35,59,17
Deleted Element is: 42
Deleted Element is: 66
Elements in the Queue are : 35,59,17
Elements in the Queue are : 35,59,17,10

Implementation of circular queue using linked list

Circular queues implemented using linked lists are flexible as the size can dynamically adjust. The front and rear pointers are used to manage the linked list, ensuring a circular structure. Enqueueing involves adding a new node at the end of the list, while memory allocation is checked to avoid overflow.
In enqueue there will be any of two cases seen while inserting a new node:
A. Insertion in an empty list
B. Insertion in a non-empty list/ normal insertion

A. Insertion in an empty list: This step is to check if the list is empty and if true, we make the front pointer or head pointer to point to the newly created block. The first node is also the last node of the list. That being the case we make our rear pointer to point to the same block to mark the end of the list.
B. Insertion in a non-empty list/ normal insertion: If the list is not empty we simply add the new node to the end of the list. We know that the last node is pointed by the rear pointer. So we make the next pointer of the rear pointer to point to the new block: rear->next = rear -> next = newNode. On insertion of a new node to the list, the rear pointer becomes the second last node. We make it point to the last node by rear = newNode.

Once the new node is added to the list we must link the rear pointer point to the front pointer to form the circular queue. Hence, at the end we do rear->next=front;

*In the dequeue function, we check if the list is empty by verifying if the front pointer is NULL. If it is, we exit. Otherwise, we retrieve the first element using the front pointer and store it in a variable called deleted_item. To remove the frontNode from the list, we update the front pointer to point to the next element or NULL if the list becomes empty. The rear pointer is adjusted accordingly. If the deleted item was the last element, both the front and rear pointers are set to NULL. Finally, we return the deleted item. Following is the implementation code:

#include<stdio.h>
#include<stdlib.h>
struct node  
{  
    int val;  
    struct node *next;  // to link the next node
}; 

struct node *front=NULL;  
struct node *rear=NULL;  
void enqueue(int item);
int dequeue();
int isEmpty();

void enqueue(int item)  
{  
    struct node *newNode;  
    newNode=(struct node *)malloc(sizeof(struct node));
    if(newNode == NULL){
      printf("Memory Overflow\n");
    return;
   }
    newNode -> val = item;  
    newNode -> next = NULL;  
    if(front == NULL)  // checking whether the Queue is empty or not.  
    {  
        front = newNode;  
    }  
    else  
    {  
        rear -> next = newNode;  
     }
        rear = newNode;
        rear->next=front; 
}  

int dequeue()  
{  
    struct node *frontNode; 
    int deleted_item;
    if(isEmpty()) 
    {  
        printf("Queue Underflow\n");  
        exit(1);    
    }
    frontNode = front; 
    deleted_item = frontNode -> val;

    if(front == rear){
        front = rear = NULL;
    } else{
        front = front -> next;
        rear -> next = front;
    }
    free(frontNode);
    return deleted_item;
  }  

int isEmpty()  
{  
    return ( (front == NULL) ? 1 : 0); 
}  

void display()  
{  
    struct node *ptr;
    if(isEmpty())  
    {  
        printf("Queue is empty\n.");  
    return;
    }  
   ptr = front;

        printf("\nElements in the Queue are :");  
        while( ptr -> next != front )  
        {  
            printf("%d, ", ptr -> val);  
            ptr = ptr -> next;  
        }  
        printf("%d\n", ptr -> val);

}

int main()  
{
    // Insert elements : 42, 66, 35
    enqueue(42);
    enqueue(66);
    enqueue(35);
    display();
    // Delete all of them
    printf("Deleted Element is: %d\n",dequeue());
    printf("Deleted Element is: %d\n",dequeue());
    printf("Deleted Element is: %d\n",dequeue());
    display();
    // Insert 10
    enqueue(10);
    display();
   // Try deleting an element in an empty circular queue.
    printf("Deleted Element is: %d\n",dequeue());
    return 0;  
} 

Output

Elements in the Queue are : 42,66,35
Deleted Element is: 42
Deleted Element is: 66
Deleted Element is: 35
Queue is empty
Elements in the Queue are : 10
Queue Underflow

Future-Proof Your Coding Skills! Join Our Best DSA Course for In-Depth Algorithmic Understanding. Enroll Now!

Summary

Let us summarize what we have learnt in this article. Circular queue is a queue with a ring-like structure where the queue end is connected to the queue start. The queue operations in circular queues are similar to basic queues with an advantage to move the queue pointers from queue end to queue start once the queue end is reached and the queue is not completely full. It can be implemented using an array or a circular linked list. The time complexity for each queue operation takes O(1).

See Also

• Circular Queue Program in C