Circular Queue in C: How to Implement?

The data is arranged in a circular queue in a circular pattern where the last element is connected to the first element. Unlike the linear queue where the tasks are executed on FIFO (First In First Out), the circular queue order of task execution may change. Insert and Delete operations can be done in any position.

The circular queue is more efficient than the linear queue. In the graphical representation of a circular queue, you can observe that the front and rear positions are connected, making it a circle wherein the operations are always executed on a FIFO basis. Every new element is added at the rear end and deleted from the front end. A circular queue has a better utilization and has a time complexity of O(1).

Source

Applications of a Circular Queue

  • CPU Scheduling: Circular queues make the use of the empty memory spaces that are found in the linear queues.
  • Traffic System: In the traffic system, with the help of the circular queues, traffic lights are operated at the set interval of time.
  • Memory Management: Operating systems frequently keep up a line of processes that are prepared to execute or that are waiting for a specific event to occur.

Learn: C Program For Bubble Sorting: Bubble Sort in C

Sample Code with Explanation

Line 1: // (1) Preprocessors

Line 2: // Set Queue Limit to 5 elements

Line 3: #include<stdio.h>

Line 4: #define LIM 5

Line 5: // (2) Queue Datatype Declarations

Line 6: // data holds data; delPos, position to delete from; length, no. of

Line 7: // elements currently present in queue

Line 8: typedef struct queue {

Line 9: int data[LIM], delPos, length;

Line 10: } Q;

Line 11: // (3) Global Declarations

Line 12: // Functions & global variable q of struct queue type

Line 13: Q q;

Line 14: void ui_Q_Ops(), insertQel(), deleteQel(), displayQels(), initQ();

Line 15: // (4) Calls UI Function after initialization

Line 16: int main()

Line 17: {

Line 18: initQ();

Line 19: ui_Q_Ops();

Line 20: return 0;

Line 21: }

Line 22: // (5) Initialize queue

Line 23: void initQ()

Line 24: {

Line 25: q.length = 0;

Line 26: q.delPos = 0;

Line 27: }

Line 28: // (6) Menu Driven Loop calls correct functions

Line 29: void ui_Q_Ops()

Line 30: {

Line 31: int choice=0;

Line 32: char input[16];

Line 33: while(choice!=4){

Line 34: printf(” \n ———————-\n “);

Line 35: printf(” 1. Insert into queue \n “);

Line 36: printf(” 2. Delete from queue \n “);

Line 37: printf(” 3. Display queue items \n “);

Line 38: printf(” 4. Exit program \n “);

Line 39: printf(” Enter choice : “);

Line 40: if (fgets(input, 15, stdin) != NULL){

Line 41: if (sscanf(input, “%d”, &choice) == 1){

Line 42: switch(choice){

Line 43: case 1: insertQel();

Line 44: break;

Line 45: case 2: deleteQel();

Line 46: break;

Line 47: case 3: displayQels();

Line 48: break;

Line 49: case 4: return;

Line 50: default: printf(“Invalid choice\n “);

Line 51: continue;

Line 52: }

Line 53: } else

Line 54: printf(” Invalid choice \n “);

Line 55: }

Line 56: }

Line 57: }

Line 58: // (7) Insert into Queue

Line 59: // If length is same as MAX Limit, the queue is full, Otherwise insert

Line 60: // circularly achieved with sum length and delPos modulus by MAX Limit

Line 61: // and increment length

Line 62: void insertQel()

Line 63: {

Line 64: int el, inspos;

Line 65: char input[16];

Line 66: if (q.length == LIM){

Line 67: printf(” Queue is full \n “);

Line 68: return;

Line 69: }

Line 70: inspos = (q.delPos + q.length) % LIM;

Line 71: printf(” Enter element to insert: “);

Line 72: if (fgets(input, 15, stdin) != NULL){

Line 73: if (sscanf(input, “%d”, &el)){

Line 74: q.data[inspos] = el;

Line 75: q.length++;

Line 76: } else

Line 77: printf(” Invalid input \n “);

Line 78: }

Line 79: }

Line 80: // (8) Delete from Queue

Line 81: // If Length is 0, queue is empty, otherwise delete at delPos

Line 82: // and decrement length

Line 83: void deleteQel()

Line 84: {

Line 85: if (q.length == 0){

Line 86: printf(” Queue is empty \n “);

Line 87: } else {

Line 88: printf(” Deleted element %d \n “, q.data[q.delPos]);

Line 89: q.delPos = (q.delPos + 1) % LIM;

Line 90: q.length–;

Line 91: }

Line 92: }

Line 93: // (9) Display Queue elements

Line 94: // Display in a circular manner running a loop starting at delPos

Line 95: // and adding iterator and modulus by Max Limit

Line 96: void displayQels()

Line 97: {

Line 98: int i;

Line 99: if (q.length == 0){

Line 100: printf(” Queue is empty \n “);

Line 101: } else {

Line 102: printf(” Elements of queue are: “);

Line 103: for(i = 0; i < q.length; i++){

Line 104: printf(“%d “, q.data[(q.delPos+i)%LIM]);

Line 105: }

Line 106: printf(” \n “);

Line 107: }

Line 108: }

Line 109:

Outputs:

Operations on a Circular Queue

1. insertQel() – Inserting an element into the Circular Queue

In a circular queue, the enQueue() function is used to insert an element into the circular queue. In a circular queue, the new feature is always inserted in the rear position. The enQueue() function takes one integer value as a parameter and inserts it into the circular queue. The following steps are implemented to insert an element into the circular queue:

Step 1 – Check if the length is the same as MAX Limit. If true, it means that the queue is FULL. If it is FULL, then display ” Queue is full ” and terminate the function.

Step 2 – If it is NOT FULL, then insert the value that’s circularly achieved with sum length and delPos modulus by MAX Limit and increment length

2. deleteQel() – Deleting an element from the Circular Queue

In a circular queue, deQueue() is a function used to delete an element from the circular queue. In a circular queue, the element is always deleted from the front position. The deQueue() function doesn’t take any value as a parameter. The following steps are implemented to delete an element from the circular queue…

Step 1 – Check whether queue is EMPTY. (front == -1 && rear == -1)

Step 2 – If it is EMPTY, then display “Queue is empty” and terminate the function.

Step 3 – If it is NOT EMPTY, then display deleted elements according to the positions. After every element is added, move on to the next position mod queue limit.

3. displayQels() – Displays the Queue elements that are present in the Circular Queue. The following steps are implemented to display the elements of a circular queue:

Step 1 – Check whether the queue is EMPTY.

Step 2 – If length is 0, it is EMPTY, then display “Queue is empty” and terminate the function.

Step 3 – If it is NOT EMPTY, then define an integer variable ‘i.’

Step 4 – Set i to 0.

Step 5 – Again, display elements according to position and increment value by one (i++). Repeat the same until ‘i <q.length’ becomes FALSE.

Circular Queue can be implemented by using the linked list as well. The following are the algorithms:

  • Algorithm for Enqueue:

if (FRONT == NULL) // Inserting in an Empty Queue

FRONT = REAR = newNode

end if

else

REAR -> next = newNode // Inserting after the last element

REAR = newNode

end else

REAR -> next = FRONT

End Enqueue

  • Algorithm for Dequeue:

if(FRONT == NULL) // Condition for underflow

Print “Queue Underflow”

end Dequeue

end if

else if(FRONT == REAR) // The queue contains only one node

temp = FRONT -> data

free(temp)

FRONT = FRONT -> next

REAR -> next = FRONT

end if

else if (FRONT == N – 1) // If FRONT is the last node

front = 0 // Make FRONT as the first node

end if

end Dequeue

Also Read: Python Vs C: Complete Side-by-Side Comparison

Conclusion

Data Structures and Algorithms are of great importance and not just in C programming but also in other languages. Its value is unprecedented, and for topics of such importance, it is better to invest in courses designed and mentored by experts, which will provide excellent value addition to your portfolio. upGrad offers a wide range of power-packed courses that not only enhance your skills but builds strong pillars of basics.

It is designed by the highly reputed IIIT-B, where they not only provide premium quality content but also make you a part of a strong network where you will connect with people who are evolving in the same career path as well as the industry experts who resolve your doubts and support you every time.

Getting to know their mentality and thought process would help you. And one of the unique things you get at upGrad is that you can opt for EMI options and go easy on your pockets.

We hope you will have an excellent learning opportunity in executing these C projects. If you are interested to learn more and need mentorship from industry experts, check out upGrad & IIIT Banglore’s PG Diploma in Full-Stack Software Development.

Prepare for a Career of the Future

UPGRAD AND IIIT-BANGALORE'S PG DIPLOMA IN FULL STACK SOFTWARE DEVELOPMENT
Apply Now

Leave a comment

Your email address will not be published. Required fields are marked *

×