#implementation-of-queue-using-linked-list

Implementation of Queue Using Linked List in C - Data Structures

Welcome to DeveloperIndian.com! In this tutorial, we will explore how to implement a Queue using a Linked List in the C programming language. Queues are an essential data structure, often used to manage data in a First-In-First-Out (FIFO) order. By leveraging a linked list, you can efficiently manage dynamic data in a queue structure.

What is a Queue?

A Queue is a linear data structure that operates on the FIFO (First In, First Out) principle. In simpler terms, the first element added to the queue is the first one to be removed. Queues are commonly used in scenarios like scheduling, task management, and buffering.

When implemented using a Linked List, queues provide the following benefits:

1. Dynamic memory allocation (no fixed size limit).
2. Efficient insertion and deletion operations.

A queue using a linked list supports the following basic operations:

• Enqueue: Insert an element at the rear of the queue.
• Dequeue: Remove an element from the front of the queue.
• Print: Display all elements of the queue.

Queue Implementation Using Linked List in C

Below is a complete implementation of a queue using a linked list in C. This code includes the essential operations of enqueue, dequeue, and display:

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

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

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

// Function to enqueue an element
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;
        return;
    }
    rear->next = newNode;
    rear = newNode;
}

// Function to dequeue an element
int dequeue() {
    if (front == NULL) {
        printf("\nQueue is Empty\n");
        return -1;
    }
    struct Node* temp = front;
    int data = front->data;
    front = front->next;

    if (front == NULL)
        rear = NULL;

    free(temp);
    return data;
}

// Function to display the queue
void display() {
    struct Node* temp = front;
    if (front == NULL) {
        printf("\nQueue is Empty\n");
        return;
    }
    printf("\nQueue elements: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    int choice, value;
    do {
        printf("\n1. Enqueue\n2. Dequeue\n3. Display\n0. Exit\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter the value to enqueue: ");
                scanf("%d", &value);
                enqueue(value);
                break;
            case 2:
                value = dequeue();
                if (value != -1) {
                    printf("Dequeued element: %d\n", value);
                }
                break;
            case 3:
                display();
                break;
            case 0:
                printf("Exiting...\n");
                break;
            default:
                printf("Invalid choice!\n");
        }
    } while (choice != 0);

    return 0;
}

Explanation of the Code

1. Structure Definition:

   • The Node structure represents each node of the linked list. Each node contains data and a pointer to the next node.

2. Global Pointers:

   • front: Points to the front of the queue.
   • rear: Points to the rear of the queue.

3. enqueue():

   • Dynamically allocates memory for a new node.
   • Adds the node at the rear of the queue.
   • Updates the rear pointer.

4. dequeue():

   • Removes the node at the front of the queue.
   • Updates the front pointer.
   • Frees the memory of the dequeued node.

5. display():

   • Traverses the linked list starting from the front pointer and prints all elements in the queue.

6. Main Function:

   • Provides a user-friendly menu for enqueue, dequeue, and display operations.

Advantages of Using Linked List for Queue

• Dynamic Size: Unlike arrays, linked lists do not have a fixed size, making them ideal for queues where the size is unpredictable.
• Efficient Operations: Insertion and deletion operations have a time complexity of O(1).

Key Applications of Queues

1. CPU Scheduling: Queues are used in process scheduling.
2. Data Buffering: Used in buffering streams like files, I/O, and packets.
3. Task Management: Handling tasks in multithreading and event-driven systems.
4. Breadth-First Search (BFS): Queues are integral in graph traversal algorithms.

Conclusion

In this article, we implemented a Queue using a Linked List in C. This dynamic implementation allows the queue to grow or shrink as required. Queues are versatile data structures with numerous real-world applications, making them an essential concept in computer science and programming.

For more tutorials and examples on Data Structures, stay tuned to DeveloperIndian.com!