DSA Tutorial

QUEUE USING LINKED LIST

🔲 Queue using Linked List in DSA

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle. In a queue, the first element added is the first to be removed. While a queue can be implemented using an array, it can also be implemented using a linked list. The linked list-based implementation offers dynamic memory allocation, where memory is only allocated when required.

Queue Implementation using Linked List

In the linked list implementation, we use two pointers: front and rear. The front pointer points to the front element of the queue, while the rear pointer points to the last element. The new elements are always inserted at the rear, and elements are dequeued from the front.

#include 
#include 

// Define the Node structure
struct Node {
    int data;
    struct Node* next;
};

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

// Function to initialize the queue
void initQueue(struct Queue* q) {
    q->front = NULL;
    q->rear = NULL;
}

// Function to enqueue (add to the rear)
void enqueue(struct Queue* q, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Enqueued %d\n", value);
}

// Function to dequeue (remove from the front)
int dequeue(struct Queue* q) {
    if (q->front == NULL) {
        printf("Queue Underflow\n");
        return -1;
    }

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

    // If the queue is empty after dequeue
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return dequeuedData;
}

// Function to peek the front element
int peek(struct Queue* q) {
    if (q->front == NULL) {
        printf("Queue is Empty\n");
        return -1;
    }
    return q->front->data;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* q) {
    return (q->front == NULL);
}

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

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

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

    return 0;
}

Applications of Queue (Linked List-based)

The linked list-based queue is highly efficient in scenarios where the size of the queue can change dynamically. Some use cases include:

Dynamic Task Scheduling: Where the queue size may vary based on incoming tasks.
Printer Queue: Dynamically handle multiple print jobs without worrying about memory constraints.
Message Queueing: Message-oriented middleware uses queues for transferring messages between processes.
Network Packets: Packets are queued in network communication systems for efficient data transfer.

🚀 Advantages of Linked List-based Queue:
- No fixed size: Can dynamically grow or shrink as needed.
- Efficient memory usage: Memory is allocated only when required.
- Avoids overflow issues that occur in array-based queues when the size limit is reached.

🚀 Try Implementing Linked List Queue:
- Add a function to display the entire queue.
- Modify the queue implementation to support priority-based queuing.
- Implement a circular linked list to optimize the queue further.

🌟 Enjoyed Learning with Us?

Help others discover Technorank Learning by sharing your honest experience.
Your support inspires us to keep building!