Queue Implementation Using Linked List in DSA C - Build from Scratch

Queue Implementation Using Linked List

📖 Scenario: Imagine a line at a ticket counter where people join at the end and get served from the front. This is how a queue works. We will build a queue using a linked list in C to manage this line efficiently.

🎯 Goal: Create a queue using a linked list in C. You will add elements to the end and remove elements from the front, then print the queue to see the order of people waiting.

📋 What You'll Learn

Define a Node struct with an integer data and a pointer to the next node called next.

Create a Queue struct with pointers front and rear to track the start and end of the queue.

Write a function enqueue to add a new node with given data at the rear of the queue.

Write a function dequeue to remove the node from the front of the queue.

Write a function printQueue to display all elements from front to rear.

Demonstrate the queue by enqueuing and dequeuing elements and printing the queue.

💡 Why This Matters

🌍 Real World

Queues are used in real life for managing lines, like customers waiting for service or tasks waiting to be processed.

💼 Career

Understanding queue implementation helps in software development roles where managing ordered data efficiently is important, such as in operating systems, network programming, and event handling.

1

Define Node and Queue Structures

Define a struct Node with an int data and a struct Node* next. Then define a struct Queue with two pointers: front and rear, both of type struct Node*.

DSA C

# Define struct Node and struct Queue
// Your code here

Hint

Think of Node as a box holding a number and a pointer to the next box. The Queue keeps track of the first and last boxes.

2

Initialize Queue and Write Enqueue Function

Create a function initQueue that returns a pointer to a new Queue with front and rear set to NULL. Then write a function enqueue that takes a pointer to Queue and an int data, creates a new Node with this data, and adds it to the rear of the queue.

DSA C

#include 
#include 

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

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

// Write initQueue and enqueue functions below
// Your code here

Hint

When the queue is empty, both front and rear point to the new node. Otherwise, add the new node after rear and update rear.

3

Write Dequeue and Print Functions

Write a function dequeue that removes the node from the front of the queue and frees its memory. If the queue becomes empty, set rear to NULL. Also write a function printQueue that prints all elements from front to rear separated by arrows -> and ends with NULL.

DSA C

#include 
#include 

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

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

struct Queue* initQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void enqueue(struct Queue* q, int data) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = temp;
        q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

// Write dequeue and printQueue functions below
// Your code here

Hint

Remove the front node and update pointers. For printing, move from front to rear printing each data followed by an arrow.

4

Test Queue Operations and Print Final Queue

In main, create a queue using initQueue(). Enqueue the integers 10, 20, and 30 in that order. Then dequeue one element. Finally, call printQueue to display the current queue.

DSA C

#include 
#include 

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

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

struct Queue* initQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}

void enqueue(struct Queue* q, int data) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->data = data;
    temp->next = NULL;
    if (q->rear == NULL) {
        q->front = temp;
        q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

void dequeue(struct Queue* q) {
    if (q->front == NULL) {
        return;
    }
    struct Node* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
}

void printQueue(struct Queue* q) {
    struct Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    // Create queue and perform operations
    // Your code here
}

Hint

Remember to enqueue 10, 20, 30 in order, then dequeue once, and finally print the queue.