C Program to Implement Queue Using Linked List

1. Introduction

A queue is a linear data structure that follows the First In First Out (FIFO) principle. This means that the first element added to the queue will be the first element to be removed. Using linked lists, we can implement a queue that can grow dynamically without needing to specify its size upfront.

2. Program Overview

In this program, we will:

1. Define a node structure for our linked list.

2. Implement the following queue operations using a linked list:

- Enqueue: To add an element to the end of the queue.

- Dequeue: To remove the first element from the queue.

- Peek: To view the first element without removing it.

- Display: To display the elements of the queue.

3. Code Program

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

// Define the structure for our linked list node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Pointers to the front and rear of our queue
Node* front = NULL;
Node* rear = NULL;

// Function to add an element to the queue
void enqueue(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Queue Overflow. Unable to allocate memory.\n");
        return;
    }
    newNode->data = value;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

// Function to remove an element from the queue
int dequeue() {
    if (front == NULL) {
        printf("Queue Underflow. Queue is empty.\n");
        return -1;
    }
    Node* temp = front;
    int dequeuedData = temp->data;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
    return dequeuedData;
}

// Function to get the first element of the queue
int peek() {
    if (front == NULL) {
        printf("Queue is empty.\n");
        return -1;
    }
    return front->data;
}

// Function to display the queue
void display() {
    Node* temp = front;
    if (temp == NULL) {
        printf("Queue is empty.\n");
        return;
    }
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("First element: %d\n", peek());
    display();
    printf("Dequeued element: %d\n", dequeue());
    display();
    return 0;
}

Output:

First element: 10
10 20 30
Dequeued element: 10
20 30

4. Step By Step Explanation

1. We begin by defining a node structure for our linked list. Each node contains an integer data and a pointer to the next node.

2. Our front pointer points to the beginning of the queue and rear pointer points to the end, both initially NULL (indicating an empty queue).

3. The enqueue function creates a new node, checks if memory allocation is successful, and then adds the new node to the end of the queue.

4. The dequeue function removes the front element from the queue, adjusts the front pointer, and if the queue becomes empty, also sets the rear pointer to NULL.

5. The peek function simply returns the data of the front node without modifying the queue.

6. The display function iterates through the linked list (queue) and prints all the elements.

7. In the main function, we demonstrate enqueuing elements into the queue, viewing the first element, dequeuing an element, and displaying the queue.