Implement Circular Queue using Linked List

#include <stdio.h>
#include <stdlib.h>

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

// Front and rear pointers
struct Node *front = NULL;
struct Node *rear = NULL;

// Function to add an element to the queue (enqueue)
void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    // Check if queue is empty
    if (front == NULL) {
        front = newNode;
    } else {
        rear->next = newNode;
    }
    rear = newNode;
    rear->next = front; // Point rear's next to front to make it circular
    printf("%d enqueued to the queue.\n", value);
}

// Function to remove an element from the queue (dequeue)
void dequeue() {
    if (front == NULL) {
        printf("Queue is empty. Cannot dequeue.\n");
        return;
    }

    // Case: Only one element in the queue
    if (front == rear) {
        printf("%d dequeued from the queue.\n", front->data);
        free(front);
        front = rear = NULL;
    } else {
        struct Node* temp = front;
        front = front->next;
        rear->next = front; // Maintain circular link
        printf("%d dequeued from the queue.\n", temp->data);
        free(temp);
    }
}

// Function to display the elements of the queue
void display() {
    if (front == NULL) {
        printf("Queue is empty.\n");
        return;
    }

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

// Main function to test the circular queue
int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    dequeue();
    display();
    enqueue(40);
    display();
    dequeue();
    display();

    return 0;
}

Explanation :

1. Node Structure:
   • Each node has an integer data and a pointer next that points to the next node.
   • struct Node is used to define this structure.
2. Front and Rear Pointers:
   • front points to the first element in the queue.
   • rear points to the last element in the queue.
3. Enqueue Operation:
   • A new node is created using malloc.
   • If the queue is empty (front is NULL), the front and rear both point to this new node.
   • Otherwise, the new node is added after the rear, and rear is updated to this new node.
   • To maintain the circular nature, rear->next is set to front.
4. Dequeue Operation:
   • If the queue is empty (front is NULL), print an error message.
   • If there is only one element (front == rear), free the node and set front and rear to NULL.
   • Otherwise, remove the front node, update front to front->next, and set rear->next to front to maintain the circular link.
5. Display Function:
   • If the queue is empty, print a message.
   • Otherwise, use a temporary pointer temp to traverse the queue starting from front, and print each node’s data until we reach front again.
6. Main Function:
   • Performs a few enqueue and dequeue operations and displays the queue’s contents to demonstrate how the circular queue works.

10 enqueued to the queue.
20 enqueued to the queue.
30 enqueued to the queue.
Queue elements: 10 20 30 
10 dequeued from the queue.
Queue elements: 20 30 
40 enqueued to the queue.
Queue elements: 20 30 40 
20 dequeued from the queue.
Queue elements: 30 40 

How the Circular Nature Works

• When adding elements, the rear->next always points back to front, creating a circle.
• When removing elements, even as front moves forward, rear still points back to the updated front, keeping the circular link intact.
• This structure allows the queue to wrap around in a circular manner, hence the name “circular queue.”