Circular Queue using Linked List

 

🌀 What is a Circular Queue?

• A circular queue is a special type of queue where the last node is connected back to the first node to make a circle.

• It helps efficiently utilize the memory — when we reach the end, we wrap around to the beginning if there is free space.

• It follows FIFO (First In First Out) like a normal queue.

✅ Using a linked list, we can model this naturally because linked lists are dynamic — we can add/delete nodes without worrying about fixed size.

---

✍️ Basic Operations

1. Enqueue (Insert):

   • Add a new element at the rear.

2. Dequeue (Delete):

   • Remove an element from the front.

3. Display:

   • Show all elements from front to rear (wrapping around if needed).

---

Algorithm to implement Circular Queue using Linked List

1. Node Structure:

• Each node contains data and next pointer.

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

2. Enqueue (Insert at Rear):

• Create a new node.

• If queue is empty, make both front and rear point to the new node. Set rear->next = front.

• Else, insert the new node after rear, update rear, and link rear->next to front.

3. Dequeue (Delete from Front):

• If queue is empty, show underflow.

• If only one node (front == rear), delete it and make front and rear NULL.

• Else, move front to front->next, update rear->next = front, and free old front node.

4. Display:

• Start from front and move till you reach back to front again.

C Program Circular Queue using Linked List

#include <stdio.h>

#include <stdlib.h>

// Node structure

struct Node {

    int data;

    struct Node* next;

};

struct Node *front = NULL, *rear = NULL;

// Enqueue function

void enqueue(int value) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;

    newNode->next = NULL;

    if (front == NULL) {

        front = rear = newNode;

        rear->next = front; // Circular link

    } else {

        rear->next = newNode;

        rear = newNode;

        rear->next = front; // Keep it circular

    }

    printf("Inserted %d\n", value);

}

// Dequeue function

void dequeue() {

    if (front == NULL) {

        printf("Queue is Empty\n");

        return;

    }

    if (front == rear) { // Only one node

        printf("Deleted %d\n", front->data);

        free(front);

        front = rear = NULL;

    } else {

        struct Node* temp = front;

        printf("Deleted %d\n", temp->data);

        front = front->next;

        rear->next = front;

        free(temp);

    }

}

// Display function

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

int main() {

    int choice, value;

    while (1) {

        printf("\n1. Enqueue\n2. Dequeue\n3. Display\n4. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter value to insert: ");

                scanf("%d", &value);

                enqueue(value);

                break;

            case 2:

                dequeue();

                break;

            case 3:

                display();

                break;

            case 4:

                exit(0);

            default:

                printf("Invalid choice!\n");

        }

    }

    return 0;

}