[Follow here] for daily coding insights.

DSA Series Chapter 7 – Circular Queue Using Linked List (C Version)

1. Introduction

A Circular Queue is a special type of queue where the last node points back to the first node, forming a circle. When implemented using a linked list, we avoid overflow due to fixed size (as in arrays).

Why Circular Queue?

Efficiently uses memory
Eliminates the “false overflow” that happens in linear queues
Useful in CPU scheduling, buffering, and round-robin-based processes

2. Node Structure in C

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

Explanation

data → stores integer value
next → pointer that links to the next node in the circle

3. Circular Queue Structure

struct CircularQueue {
    struct Node* front;
    struct Node* rear;
};

Meaning of Members

front → points to the first node from where deletion happens
rear → points to the last node where insertion happens
In a circular queue:
```
rear->next == front;
```

4. Initialization

void initQueue(struct CircularQueue* q) {
    q->front = q->rear = NULL;
}

5. Enqueue Operation (Insert)

void enqueue(struct CircularQueue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;

    if (q->front == NULL) {
        // First element
        q->front = q->rear = newNode;
        newNode->next = newNode; // Circular link
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
        q->rear->next = q->front; // Maintain circle
    }
}

Explanation

If queue is empty:
- front = rear = newNode
- newNode->next = newNode (circle created)
Else:
- Attach new node to last
- Update rear
- Make rear->next = front (to maintain circular property)

Time Complexity: O(1)
Space Complexity: O(1) per insertion

6. Dequeue Operation (Delete)

int dequeue(struct CircularQueue* q) {
    if (q->front == NULL) {
        printf("Queue Underflow!\n");
        return -1;
    }

    int value;
    struct Node* temp = q->front;

    // Only one element
    if (q->front == q->rear) {
        value = temp->data;
        q->front = q->rear = NULL;
        free(temp);
    } else {
        value = temp->data;
        q->front = q->front->next;
        q->rear->next = q->front; // Maintain circle
        free(temp);
    }

    return value;
}

Explanation

If queue empty → underflow
If only one node:
- Remove and set both pointers to NULL
Else:
- Move front to next node
- Maintain circular link

Time Complexity: O(1)

7. Peek Operation

int peek(struct CircularQueue* q) {
    if (q->front == NULL) {
        printf("Queue is Empty!\n");
        return -1;
    }
    return q->front->data;
}

8. Display Operation

void display(struct CircularQueue* q) {
    if (q->front == NULL) {
        printf("Queue is Empty!\n");
        return;
    }

    struct Node* temp = q->front;

    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != q->front);

    printf("\n");
}

Explanation

Traverses until the pointer returns to the front node again.

9. Complete Program

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

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

struct CircularQueue {
    struct Node* front;
    struct Node* rear;
};

void initQueue(struct CircularQueue* q) {
    q->front = q->rear = NULL;
}

void enqueue(struct CircularQueue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;

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

int dequeue(struct CircularQueue* q) {
    if (q->front == NULL) {
        printf("Queue Underflow!\n");
        return -1;
    }

    struct Node* temp = q->front;
    int value = temp->data;

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

    free(temp);
    return value;
}

int peek(struct CircularQueue* q) {
    if (q->front == NULL) {
        printf("Queue is Empty!\n");
        return -1;
    }
    return q->front->data;
}

void display(struct CircularQueue* q) {
    if (q->front == NULL) {
        printf("Queue is Empty!\n");
        return;
    }

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

    printf("\n");
}

int main() {
    struct CircularQueue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    display(&q);

    printf("Dequeued: %d\n", dequeue(&q));
    display(&q);

    printf("Front element: %d\n", peek(&q));

    return 0;
}

10. Advantages of Linked List Circular Queue

> No fixed size (no overflow unless memory full)
> Efficient O(1) enqueue/dequeue
> Memory used only when needed

11. Applications

CPU Round-robin scheduling
Traffic light controllers
Circular buffers
Resource scheduling systems

Exercises (Circular Queue – Linked List)

PART A – Basic Level (10 Questions)

What is the main difference between array circular queue and linked list circular queue?
Why is rear->next = front required?
What happens during dequeue when the queue has only one node?
Draw memory representation of a circular queue with 3 nodes.
Write the algorithm for enqueue.
Write the algorithm for dequeue.
What is the time complexity of enqueue and dequeue?
Why does circular queue avoid “false overflow”?
What are applications of circular queues?
Define front and rear roles in a circular queue.