Understanding Queue in C — Linear, Circular, and Dynamic Queues

The Queue is one of the most fundamental data structures in programming. It follows the FIFO (First-In, First-Out) principle — the element added first is removed first. From CPU scheduling to printer job queues, this structure powers many essential systems in computer science.

Basic Queue Terminology

• Enqueue: Inserting an element
• Dequeue: Removing an element
• Front: Index of the element to be dequeued next
• Rear: Index where new elements are enqueued

1. Linear Queue in C

A linear queue is the simplest type of queue and uses a fixed-size array. Once the queue reaches the end of the array, even if space is available due to dequeued elements, no new element can be added unless we reset or shift the entire queue. This limitation makes it inefficient for systems where frequent insertions and deletions happen.

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value) {
    if (rear == SIZE - 1)
        printf("Queue Overflow\n");
    else {
        if (front == -1) front = 0;
        queue[++rear] = value;
    }
}

void dequeue() {
    if (front == -1 || front > rear)
        printf("Queue Underflow\n");
    else
        printf("Dequeued: %d\n", queue[front++]);
}

void display() {
    if (front == -1 || front > rear)
        printf("Queue is Empty\n");
    else {
        printf("Queue: ");
        for (int i = front; i <= rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    dequeue();
    display();
    return 0;
}

Output:

Queue: 10 20 30
Dequeued: 10
Queue: 20 30

Drawback: Even if you remove some elements, the freed-up space can't be reused unless you reset the indices. This leads to memory inefficiency.

2. Circular Queue in C

Linear queues waste space once elements are dequeued. Circular queues solve this by connecting the end back to the front like a ring.

In circular queues, the idea is to wrap around the array using modulo arithmetic. This means that when the rear of the queue reaches the end, it continues from the start of the array (if space is available), allowing reuse of previously freed locations.

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

void enqueue(int value) {
    if ((rear + 1) % SIZE == front)
        printf("Queue Overflow\n");
    else {
        if (front == -1)
            front = rear = 0;
        else
            rear = (rear + 1) % SIZE;
        queue[rear] = value;
    }
}

void dequeue() {
    if (front == -1)
        printf("Queue Underflow\n");
    else {
        printf("Dequeued: %d\n", queue[front]);
        if (front == rear)
            front = rear = -1;
        else
            front = (front + 1) % SIZE;
    }
}

void display() {
    if (front == -1)
        printf("Queue is Empty\n");
    else {
        printf("Queue: ");
        int i = front;
        while (1) {
            printf("%d ", queue[i]);
            if (i == rear) break;
            i = (i + 1) % SIZE;
        }
        printf("\n");
    }
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    dequeue();
    enqueue(50);
    display();
    return 0;
}

Output:

Dequeued: 10
Queue: 20 30 40 50

Note: Circular queues are often used in real-time systems such as buffering, where memory needs to be reused continuously without shifting elements.

3. Dynamic Queue using Linked List

To overcome fixed-size limitations, we can use a linked list for dynamic queue implementation.

Dynamic queues are implemented using linked lists. They offer the most flexibility, as memory is allocated during runtime and can grow or shrink as needed. This approach avoids the problem of overflow unless the system runs out of memory.

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

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

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

void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

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

void dequeue() {
    if (front == NULL)
        printf("Queue Underflow\n");
    else {
        struct Node* temp = front;
        printf("Dequeued: %d\n", front->data);
        front = front->next;
        free(temp);
        if (front == NULL)
            rear = NULL;
    }
}

void display() {
    if (front == NULL)
        printf("Queue is Empty\n");
    else {
        struct Node* temp = front;
        printf("Queue: ");
        while (temp != NULL) {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    enqueue(100);
    enqueue(200);
    enqueue(300);
    display();
    dequeue();
    display();
    return 0;
}

Output:

Queue: 100 200 300
Dequeued: 100
Queue: 200 300

Advantages: No pre-defined size, no overflow (until memory is exhausted), and ideal for unpredictable workloads.

Real-Life Applications of Queues

• CPU task scheduling
• Printer job queue
• Call center hold queue
• BFS traversal in graphs
• Order management in e-commerce

Conclusion

Queues are an essential tool in both theory and real-world programming. Whether you're writing a scheduler, managing memory, or building simulations, mastering queues will prepare you for advanced data structures and system-level programming.

Start with static queues, move on to circular ones for memory efficiency, and finally adopt dynamic queues for unlimited growth. Understanding these variations will strengthen your foundation in C programming and beyond.

Start with static queues, move on to circular ones for memory efficiency, and finally adopt dynamic queues for unlimited growth. Understanding these variations will strengthen your foundation in C programming and beyond.