Circular Queue Data Structure Algorithm by DeveloperIndian

A circular queue is an extended version of a regular queue in which the last element connects back to the first element, forming a circular structure. This design effectively optimizes memory usage by reusing unoccupied space from the front of the queue once elements are dequeued.

In this article, we will delve into the concept of a circular queue, its operations, and provide working examples in C for better understanding.

What Is a Circular Queue?

A circular queue is a First In First Out (FIFO) data structure that operates like a linear queue but connects the last position back to the first. This eliminates the issue of wasted space when elements are removed from the front, as the queue can now wrap around to fill empty slots.

Example Use Case

A common example is a task scheduling system where jobs are processed cyclically, and the queue needs to reuse memory efficiently without resetting.

Circular Queue Operations

1. Enqueue (Insert): Add an element to the rear of the queue.
2. Dequeue (Remove): Remove an element from the front of the queue.
3. Peek: View the front element without removing it.
4. Display: Show all elements in the queue in sequential order.

Implementation of Circular Queue in C

Below is the code for implementing a circular queue using arrays in C. This code demonstrates all the fundamental operations.

#include<stdio.h>
#include<conio.h>
#define MAX 10

int queue[MAX];
int f = -1, r = -1;

void insertrear(int no) {
    if ((f == 0 && r == MAX - 1) || (r + 1 == f)) {
        printf("\nQueue is Full");
        return;
    } else {
        if (r == -1)
            f = r = 0;
        else if (r == MAX - 1)
            r = 0;
        else
            r++;
        queue[r] = no;
    }
}

int deletefront() {
    int val;
    if (f == -1) {
        printf("\nQueue is Empty");
        return -999;
    } else {
        val = queue[f];
        if (f == r)
            f = r = -1;
        else if (f == MAX - 1)
            f = 0;
        else
            f++;
    }
    return val;
}

void show() {
    int i = f;
    if (f == -1) {
        printf("\nQueue is Empty");
        return;
    }
    while (i != MAX) {
        printf("%d  ", queue[i]);
        if (i == r)
            break;
        else if (i == MAX - 1)
            i = 0;
        else
            i++;
    }
}

void main() {
    int ch, n;
    do {
        printf("\n1. Insert in Rear");
        printf("\n2. Delete from Front");
        printf("\n3. Show");
        printf("\n0. Exit");
        printf("\n\nEnter Your Choice: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("\nEnter Number: ");
                scanf("%d", &n);
                insertrear(n);
                break;
            case 2:
                n = deletefront();
                if (n != -999)
                    printf("\n%d deleted", n);
                break;
            case 3:
                show();
                break;
            case 0:
                break;
            default:
                printf("\nWrong Choice...Try Again");
        }
    } while (ch != 0);
}

Explanation of the Code

1. Enqueue Operation:

   • Checks if the queue is full by ensuring the rear is one step behind front (circularly).
   • If empty, initializes the front and rear to 0.
   • Inserts the new element and increments rear (wrapping around if necessary).

2. Dequeue Operation:

   • Checks if the queue is empty by verifying if front is -1.
   • Retrieves the value at the front.
   • Adjusts the front index or resets both front and rear if the queue becomes empty.

3. Display Operation:

   • Loops through the queue from front to rear in a circular manner to print all elements.

Advantages of Circular Queue

• Efficient memory utilization compared to linear queues.
• No need to shift elements, as the queue is circular.
• Ideal for applications requiring continuous processing, such as traffic management, task scheduling, and caching mechanisms.

Conclusion

The circular queue is a powerful data structure that addresses memory inefficiencies in linear queues by connecting the end of the queue back to the start. This implementation, shown in C, demonstrates the practical use of enqueue, dequeue, and display operations. Circular queues are commonly used in real-world applications where memory optimization and cyclic data processing are essential.

Learn more about circular queues and other data structures at DeveloperIndian.com!