#Queue-using-C-Data-Structure

Queue Data Structure Algorithm: Comprehensive Guide with Implementation

A queue is a linear data structure that operates on the First In, First Out (FIFO) principle. It plays a crucial role in computer science and real-world applications, such as handling requests in web servers, managing processes in operating systems, and simulating real-world lines.

In this article, we will cover the fundamentals of queues, their variations, and step-by-step implementations in C. Along the way, we’ll focus on SEO-optimized keywords and practical insights for high-ranking search results.

What Is a Queue Data Structure?

A queue organizes data in a linear format, with elements being added from one end (the rear) and removed from the other (the front). This FIFO principle ensures the element enqueued first is dequeued first.

For example:

• Imagine a line of customers at a store. The first customer to join the line is the first to be served.

Key Features of a Queue

1. FIFO Principle: Elements are dequeued in the order they were enqueued.
2. Two Pointers:
   • front: Tracks the element to be dequeued.
   • rear: Tracks the last inserted element.
3. Real-World Applications:
   • CPU scheduling in operating systems.
   • Print job management.
   • Data buffering in streaming platforms.

Types of Queues

1. Simple Queue: A standard FIFO implementation.
2. Circular Queue: Overcomes the limitations of fixed-size arrays by wrapping around when reaching the end.
3. Priority Queue: Associates priorities with elements and dequeues based on priority rather than arrival order.

Circular Queue vs Priority Queue

• Circular Queue: Efficient use of memory in fixed-size implementations.
• Priority Queue: Ideal for scenarios like process scheduling, where tasks have varying priorities.

In this tutorial, we focus on the Priority Queue implemented using a linked list.

C Implementation of a Priority Queue

Below is an implementation of a Priority Queue using a linked list in C. This ensures flexibility in managing dynamic data while handling priorities efficiently.

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

struct queue {
    int no, pri;
    struct queue *next;
};

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

void insert(int val, int pr) {
    struct queue *p, *q;
    q = (struct queue *)malloc(sizeof(struct queue));
    q->no = val;
    q->pri = pr;
    if (front == NULL) {
        q->next = NULL;
        front = rear = q;
        return;
    }
    p = front;
    while ((p->next != NULL) && (p->next->pri <= q->pri)) {
        p = p->next;
    }
    if (front->pri > q->pri) {
        q->next = front;
        front = q;
    } else {
        q->next = p->next;
        p->next = q;
    }
}

int deletefront() {
    int val;
    struct queue *q;
    if (front == NULL) {
        printf("\nQueue is Empty");
        return -999;
    }
    q = front;
    val = front->no;
    if (front == rear) {
        front = rear = NULL;
    } else {
        front = front->next;
    }
    free(q);
    return val;
}

void show() {
    struct queue *q = front;
    if (front == NULL) {
        printf("\nQueue is Empty");
        return;
    }
    while (q != NULL) {
        printf("%d (Priority: %d) -> ", q->no, q->pri);
        q = q->next;
    }
    printf("NULL\n");
}

int main() {
    int ch, n, pr;
    do {
        printf("\n1. Insert");
        printf("\n2. Delete from Front");
        printf("\n3. Show");
        printf("\n0. Exit");
        printf("\n\nEnter Your Choice: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("\nEnter Number: ");
                scanf("%d", &n);
                printf("\nEnter Priority: ");
                scanf("%d", &pr);
                insert(n, pr);
                break;
            case 2:
                n = deletefront();
                if (n != -999)
                    printf("\n%d deleted", n);
                break;
            case 3:
                show();
                break;
            case 0:
                break;
            default:
                printf("\nWrong Choice");
        }
    } while (ch != 0);
    return 0;
}

How the Code Works

1. Insertion:
   • Adds an element (val) with a priority (pr).
   • Maintains the order of priority during insertion.
2. Deletion:
   • Removes the element at the front of the queue.
3. Display:
   • Traverses the queue and prints all elements along with their priorities.

Advantages of Using Linked Lists for Queues

• Dynamic Size: Linked lists adapt to changing sizes, unlike static arrays.
• Efficient Memory Usage: Memory is allocated as needed.

Applications of Priority Queues

• Operating Systems: Process scheduling based on priority.
• Networking: Packet routing based on priority.
• AI Algorithms: Pathfinding algorithms like Dijkstra’s use priority queues.

Conclusion

Queues are a fundamental data structure with extensive applications in software development and problem-solving. Whether you’re implementing a Simple Queue, Circular Queue, or Priority Queue, understanding the underlying principles is essential.

The priority queue implementation in C presented above demonstrates how to dynamically manage data with varying priorities using linked lists. By mastering such techniques, developers can optimize performance and ensure scalability in their applications.

For more tutorials on data structures and algorithms, visit developerIndian.com.