Circular Queue Program in C

What is a Circular Queue in C?

A circular queue is a linear data structure used in programming to store data. It continues to adhere to the First In First Out insertion and deletion protocol. You may be familiar with the queue data structure, which similarly follows the FIFO principle and is a linear data structure; however, the difference between a circular queue and a normal queue is that the last element of the queue is logically or physically remains linked to the first element, resulting in a circular connection. That's why it is called Circular + Queue.

Why Circular Queue?

This should be the next question in your mind if we have a queue for the same purpose then why we are using a circular queue and why do we want to connect the last and first element? Actually, in programming, we always tend to optimize the data structures and algorithms in terms of either time complexity or space complexity. Let's recall the scenario of a normal queue,

• We declare the queue with some initial size and according to the construction of the queue, the rear and front pointers start pointing to the initial position.
• As soon as we insert an element the rear pointer moves to one index or position away from the front pointer. In this way, if we keep inserting the elements the rear will be that many positions away from the front.
• Now let's start the de-queue operation during the deletion of an element from the front. With shifting one position, the front pointer approaches the rear pointer and points to the next front element. In this manner, the front pointer also proceeds forward.

We can see both pointers are moving towards the forwarding direction or can say left to right so, what to do with the space which is left blank at the left side of the front pointer, we can never use them traditionally because insertion will always happen at the rear. The possible solution could be,

• We can empty the entire queue so that the front and rear will come to the starting position of the queue.
• We can shift the entire queue backward.
• We can implement some functionality that can deallocate the space used by the blocks earlier to the front pointer.

All of the approaches outlined above have extra overhead, so a circular queue was introduced to address this issue, when the rear pointer reaches the end position of the allocated space and if there is some unused memory space then the rear pointer shifts to the first position in this way the remaining space is being utilized.

How To Implement Circular Queue in C?

We can create the circular queue in C using either arrays or linked lists. In this article, we will implement a circular queue program in c only using arrays.

Operations on a Circular Queue

The Circular Queue supports two basic operations: inserting an element (called enqueue) and removing an element from the queue (called dequeue). Two pointers, front, and rear (sometimes called back), are needed to maintain details of where insertion and deletion will actually occur. When the queue is empty, both pointers either point to NULL or we assign -1 to indicate that the queue is empty.

enQueue Operation in Circular Queue

The enqueue operation means inserting some element into the queue, with every valid enqueue operation the rear pointer keeps incrementing.

Example 1: Insertion of element on empty Circular Queue.

If initially, the queue is empty then on the first insertion the front and rear will be set to the initial position and both will point to the same element.

Example 2: Insertion of element when already there are some elements in Circular Queue.

In such a case, the rear pointer will keep incrementing for each insertion.

Example 3: Insertion of element when the rear pointer is already at the end of the queue but still there is some space remaining for insertion.

If increment of the rear pointer is not possible but there is enough space for insertion, the rear pointer shifts towards $0^{th}$ index or first position.

Pseudo Code

Time & Space Complexity

In the insertion, we just increment the rear pointer and assign a value to already allocated memory, these both sub-operations are constant hence, the time complexity of the insertion operation is constant O(1).

Also, there is no need for extra space while insertion, so space complexity is also constant O(1).

deQueue Operation in Circular Queue

The dequeue operation means deleting some element from the queue, With every valid dequeue operation, the front pointer keeps incrementing.

Example 1: Deletion of the element from non-empty Circular Queue.

During deletion, the value corresponding to the front pointer is removed and the front pointer keeps incrementing.

Example 2: Deletion of the element, when the front pointer is already at the last position of the non-empty Circular Queue, and further increment of position is not possible.

In the circular queue, both pointers can circularly take the positions so, the front pointer will shift to the first position of the circular queue.

Pseudo Code

Time & Space Complexity

In the algorithm, only the value at the memory space located by the front pointer is removed and the front pointer is incremented. The time complexity is constant O(1) because we are not performing any intensive steps, memory release and increment both are constant sub-operations.

Also, there is no need to store or allocate some extra memory for deletion operation hence space complexity is also constant O(1).

Program of Circular Queue Program in C using Array

Output:

Explanation:

• Let's start the discussion of the circular queue program in c from the main function, we have initially assigned 6 to the global variable named size. It will represent the size of the queue.
• Up next we are trying to allocate the memory to create an array of size 6. The base address of the array which is returned by malloc is assigned to a global pointer variable named circularQueue.
• The reason here we are using global variables is that we want our variables to be accessible by every function.
• Further we are using a user-defined macro to print the value of the front and rear variables, skip this if you are unaware of macros.
• Initially we have nothing in the circular queue so the front and rear both will contain -1.
• Up next we are inserting 8 in the queue by using enQueue function. So front and rear will both contain 0 as an index, which means both will point to the memory block containing value 8.
• At each enQueue operation the rear pointer will keep incrementing.
• After a few insertions, we are printing the entire queue with the help of the display function, the reason we are providing front and rear pointers here is that inside the function they will get manipulated that's why we are passing them as parameters so they can act as a local variable inside the function and the changes don't get reflected globally.
• With each dequeue operation the front will increment to point towards the next element and the element which was earlier stored at the place where deletion happened will contain a default value as 0, and we cannot access that.

Applications of a Circular Queue

There could be several real life examples of circular queues two of them are given below,

Process Scheduling in Operating System

The Operating System implements a process scheduling algorithm to provide the CPU to a particular process for execution.

Traffic System

Traffic system can also implement the circular queue to change the status of the signal and set the delay before the status change.