Circular Queue In C Program

An important benefit that can be obtained in implementing a circular queue is the full utilization of space. A regular queue can become full with empty slots at the front since they are the elements that are first dequeued. This challenge is addressed in circular queues as the first element location always follows the last location and doesn’t waste space. This makes circular queues very useful wherever memory is scarce or where there is a constant flow of data input that has to be effectively controlled.

Consider this example where elements 1 to 8 are enqueued, with the front pointing to 1 and the rear to 8. If we dequeue 1 and 2 in a linear queue, the first two memory slots become unusable. One solution to overcome this waste memory space is to shift the remaining elements forward to free up space at the end. However this approach negatively affects runtime performance. Also, when there is no shifting, the unused memory remains inaccessible. Therefore, this approachis  inefficient, especially with static arrays.

A more efficient solution is a circular queue. In a circular queue, the first position logically follows the last, forming a loop. This structure eliminates wasted space without the need for shifting. Circular queues can be implemented using a circular array, singly linked list, or doubly linked list, making them ideal for optimizing memory usage.

• Front: Retrieves the element located at the front of the queue.
• Rear: Retrieves the element located at the rear of the queue.
• enQueue(value): Inserts a new element into the queue. The insertion always happens at the rear end.
• deQueue(): Removes an element from the queue. Deletion always occurs from the front end.
• Peek: Returns the value at the front of the queue without removing it.
• IsFull: Checks if the queue is full, indicating no more elements can be added
• IsEmpty: Verifies if the queue is empty, meaning no elements are present.

Now, we’ll look closely into two important operations: enqueue and dequeue.

Enqueue Operation 

Here are the steps for performing an enqueue operation in a circular queue:

1. Check if the queue is full: If the queue is full, Check if size == capacity (queue is full), display “Queue is full”. Insertion is not possible
2. Initial Condition: When the queue is empty, use FRONT to track the first element of the queue and REAR to track the last elements of the queue. Now, initially, both front and rear are set to -1. 
3. Insert New Element: To add a new element, increment the rear pointer. In a circular queue, this is done using rear = (rear + 1) % size.

Scenarios for inserting an element

There are two scenarios in which queue is not full:

If rear != max - 1,
If front != 0 and rear = max - 1

A diagrammatic representation of it goes like this:

Pesudocode for enqueue is as follows:

ENQUEUE(queue, value):
    IF (rear + 1) % SIZE == front:
        PRINT "Queue is full!"
        RETURN
    IF front == -1:        // Queue is empty
        front = 0
        rear = 0
    ELSE:
        rear = (rear + 1) % SIZE
    queue[rear] = value

Dequeue Operation 

Here are the steps for performing a dequeue operation in a circular queue:

1. Check if the queue is empty: If the queue is empty, the dequeue operation cannot be performed. So, check using — size == 0 (queue is empty), display “Queue is empty”.
2. Remove an Element: When an element is removed, the front pointer is incremented (front = (front + 1) % size).
3. Handle Single Element Case: If the queue has only one element left to be deleted, both front and rear are reset to -1 to indicate the queue is empty.

Diagrammatically, the dequeuing operation looks as follows: 

The pseudocode for the dequeue operation is as follows:

DEQUEUE(queue):
    IF front == -1:
        PRINT "Queue is empty!"
        RETURN
    value = queue[front]
    IF front == rear:      // Only one element left
        front = -1
        rear = -1
    ELSE:
        front = (front + 1) % SIZE
    RETURN value

// C Program to implement a circular queue using arrays
#include <stdio.h>
// Define the maximum size of the queue
#define MAX_SIZE 7
// Declare the queue array and front, rear variables
int queue[MAX_SIZE];
int front = -1, rear = -1;
// Function to check if the queue is full
int isFull() {
    return (rear + 1) % MAX_SIZE == front;
}

// Function to check if the queue is empty
int isEmpty() {
    return front == -1;
}
// Function to enqueue (insert) an element
void enqueue(int data) {
    if (isFull()) {
        printf("Queue overflow\n");
        return;
    }
    if (front == -1) {
        front = 0;
    }
    rear = (rear + 1) % MAX_SIZE;
    queue[rear] = data;
    printf("Element %d inserted\n", data);
}
// Function to dequeue (remove) an element
int dequeue() {
    if (isEmpty()) {
        printf("Queue underflow\n");
        return -1;
    }
    int data = queue[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX_SIZE;
    }
    return data;
}

// Function to display the queue elements
void display() {
    if (isEmpty()) {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue elements: ");
    int i = front;
    while (i != rear) {
        printf("%d ", queue[i]);
        i = (i + 1) % MAX_SIZE;
    }
    printf("%d\n", queue[rear]);
}

// Main function
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    enqueue(50);
    enqueue(60);
    enqueue(70);
    enqueue(80);  // This should show "Queue overflow"

    display();

    printf("Dequeued element: %d\n", dequeue());
    printf("Dequeued element: %d\n", dequeue());

    display();

    enqueue(80);
    enqueue(90);  // Should be added successfully
    display();
    return 0;
}

Output:

Element 10 inserted
Element 20 inserted
Element 30 inserted
Element 40 inserted
Element 50 inserted
Element 60 inserted
Element 70 inserted
Queue overflow
Queue elements: 10 20 30 40 50 60 70
Dequeued element: 10
Dequeued element: 20
Queue elements: 30 40 50 60 70
Element 80 inserted
Element 90 inserted
Queue elements: 30 40 50 60 70 80 90


=== Code Execution Successful ===

How the code works: 

Queue Setup: A circular queue is implemented using an array of size 5.

Operations:

• enqueue(data): Inserts a new element at the rear of the queue, checking if the queue is full before adding.
• dequeue(): Removes an element from the front of the queue, checking if the queue is empty before removing.
• isFull(): Checks if the queue is full by comparing the rear pointer's next position with the front pointer.
• isEmpty(): Checks if the queue is empty by checking if the front pointer is set to -1.

Circular Queue: Uses modulo arithmetic to handle the wraparound of the front and rear pointers when the queue is full or has available space.

Display: The display() function prints the elements from the front to the rear, considering the circular structure to wrap around the array.

Output: The program enqueues and dequeues elements and prints the queue's state at each step.

// C program for insertion and deletion 
// in Circular Queue
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node *front, *rear;
};


struct Node* createNode(int newdata);

// Function to insert element in a Circular queue
void enQueue(struct Queue* q, int value) {
    struct Node* newNode = createNode(value);

    if (q->front == NULL)
        q->front = newNode;
    else
        q->rear->next = newNode;

    q->rear = newNode;
    q->rear->next = q->front;
}

// Function to delete element from Circular Queue
int deQueue(struct Queue* q) {

    // if queue is empty
    if (q->front == NULL) {
        return -1;
    }

    int value;

    // If this is the last node to be deleted
    if (q->front == q->rear) {
        value = q->front->data;
        free(q->front);
        q->front = q->rear = NULL;
    } else {
        struct Node* temp = q->front;
        value = temp->data;
        q->front = q->front->next;
        q->rear->next = q->front;
        free(temp);
    }

    return value;
}

void printQueue(struct Queue* q) {
    if (q->front == NULL) return;

    struct Node* curr = q->front;
    do {
        printf("%d ", curr->data);
        curr = curr->next;
    } while (curr != q->front);
    printf("\n");
}

// Function to return the front value
int front(struct Queue* q) {
    struct Node* front = q->front;

    if (front == NULL) {
        return -1;
    }
    
    return front->data;
}

// Function to return the rear value
int rear(struct Queue* q) {
    struct Node* rear = q->rear;

    if (rear == NULL) {
        return -1;
    }

    return rear->data;
}

struct Queue* createQueue() {
    struct Queue* q = 
    (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

struct Node* createNode(int newdata) {
    struct Node* newnode
        = (struct Node*)malloc(sizeof(struct Node));
    newnode->data = newdata;
    newnode->next = NULL;
    return newnode;
}

int main() {
    struct Queue* q = createQueue();

    enQueue(q, 14);
    enQueue(q, 22);
    enQueue(q, 6);
    enQueue(q, 20);
    
    printf("Front value: %d\n", front(q)); 
    printf("Rear value: %d\n", rear(q));

    printQueue(q);

    printf("Deleted value = %d\n", deQueue(q));
    printf("Deleted value = %d\n", deQueue(q));

    printQueue(q);

    return 0;
}

Output:

Front value: 14
Rear value: 20
14 22 6 20 
Deleted value = 14
Deleted value = 22
6 20 


=== Code Execution Successful ===

How the code works: 

This circular queue program in C a circular queue using a linked list. Here's how it works:

• Node Structure: Each queue element is represented by a node with data and a pointer (next) to the next node.
• Queue Structure: The queue holds two pointers: front (points to the first node) and rear (points to the last node).
• enQueue(): This function adds a new node to the rear of the queue. If the queue is empty, both front and rear point to the new node. Otherwise, the new node is linked to the current rear, and rear is updated. The rear's next pointer is linked back to the front to maintain the circular nature.
• deQueue(): This function removes a node from the front of the queue. If there's only one node, both front and rear are set to NULL. Otherwise, the front is updated to the next node, and the rear's next is updated to the new front.
• printQueue(): This function prints all the elements in the queue, traversing from the front back to the front in a circular manner.
• front() and rear(): These functions return the data at the front and rear of the queue, respectively, or -1 if the queue is empty.
• createQueue() and createNode(): These helper functions allocate memory for a new queue or node.

• Memory Management: Circular queues efficiently manage memory by utilising empty spaces, unlike linear queues.
• CPU Scheduling: Circular queues help the operating system manage the insertion and execution of programs.‍
• Traffic System: Circular queues control traffic lights, cycling through red, yellow, and green lights in a loop.

The circular queue in C program implementation is very important for any student and any aspiring software developer as it increases the knowledge and understanding of memory efficiency, structure design, and practical applications. This concept helps to build problem-solving abilities greatly when it comes to optimally using available resources like CPU scheduling and traffic controlling systems. It provides a good background to some of the other complicated areas in data structures and efficient algorithms. To learn more and build a solid foundation, take up the CCBP Academy 4.0 program. 

1. What is the advantage of applying the circular queue system?

Circular queues enhance memory utilisation since they work around data structures. They optimise available space without wasting memory.

2. How is a circular queue implemented?

Circular queues can be implemented by array or linked list. For realising the queue in arrays, modulo arithmetic assists in wrapping around the queue, while in linked lists, the actual structure of the link list is changed to make it form a circular chain.

3. What is the importance of circular increment in a circular queue?

Circular increment ensures that once the target queue has been reached, the next element is placed at the front, hence a continuous circular fashion.

4. Which operations are implemented in the circular queue?

The intended operations are enqueue, which means insertion of an element, and dequeue, which means deletion of an element. Front to obtain the front element and rear for the rear element and isEmpty to know whether the list is empty.

5. How are circular queues useful in data structures?

Circular queue program in C are used in many real-life applications, and these are resource allocation, buffering, scheduling, simulation, data transmission, print spooling, real-time systems, networking, and memory management.