C Program to Implement Queue Using Linked List

Introduction

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. When implementing a queue using a linked list, each element (or node) in the queue contains data and a pointer to the next node. The queue operations, such as enqueue (insert) and dequeue (remove), can be easily handled by manipulating pointers.

Example:

• Enqueue Operation: Adding elements [10, 20, 30] to the queue results in 10 being at the front and 30 at the rear.
• Dequeue Operation: Removing the front element (10) from the queue leaves 20 at the front.

Problem Statement

Create a C program that:

• Implements a queue using a linked list.
• Performs queue operations such as enqueue, dequeue, and peek.
• Displays the queue contents after each operation.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Queue Operations:

• Enqueue: Add an element to the rear of the queue.
• Dequeue: Remove and return the front element from the queue.
• Peek/Front: Return the front element without removing it.
• IsEmpty: Check if the queue is empty.

4. Create a Main Function: In the main() function, allow the user to perform queue operations interactively.

C Program to Implement Queue Using Linked List

#include <stdio.h> #include <stdlib.h> // Step 2: Define the Node Structure struct Node { int data; struct Node* next; }; // Structure to represent a queue struct Queue { struct Node *front, *rear; }; // Function to create a new node struct Node* newNode(int value) { struct Node* temp = (struct Node*)malloc(sizeof(struct Node)); temp->data = value; temp->next = NULL; return temp; } // Function to create an empty queue struct Queue* createQueue() { struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue)); queue->front = queue->rear = NULL; return queue; } // Function to check if the queue is empty int isEmpty(struct Queue* queue) { return queue->front == NULL; } // Function to add an element to the queue (enqueue) void enqueue(struct Queue* queue, int value) { struct Node* temp = newNode(value); // If the queue is empty, then the new node is both the front and rear if (queue->rear == NULL) { queue->front = queue->rear = temp; printf("%d enqueued to the queue.\n", value); return; } // Add the new node at the end of the queue and change the rear queue->rear->next = temp; queue->rear = temp; printf("%d enqueued to the queue.\n", value); } // Function to remove and return the front element from the queue (dequeue) int dequeue(struct Queue* queue) { if (isEmpty(queue)) { printf("Queue underflow! Cannot dequeue from an empty queue.\n"); return -1; // Return -1 to indicate queue underflow } struct Node* temp = queue->front; int dequeued_value = temp->data; // Move front to the next node queue->front = queue->front->next; // If the queue is now empty, set rear to NULL as well if (queue->front == NULL) { queue->rear = NULL; } free(temp); return dequeued_value; } // Function to return the front element of the queue without removing it int peek(struct Queue* queue) { if (isEmpty(queue)) { printf("Queue is empty! Cannot peek.\n"); return -1; // Return -1 to indicate an empty queue } return queue->front->data; } // Function to display the queue elements void display(struct Queue* queue) { if (isEmpty(queue)) { printf("Queue is empty!\n"); return; } struct Node* temp = queue->front; printf("Queue elements: "); while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } int main() { struct Queue* queue = createQueue(); int choice, value; while (1) { // Step 4: Provide a Menu for Queue Operations printf("\nQueue Operations Menu:\n"); printf("1. Enqueue\n"); printf("2. Dequeue\n"); printf("3. Peek\n"); printf("4. Display\n"); printf("5. Exit\n"); printf("Enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: printf("Enter value to enqueue: "); scanf("%d", &value); enqueue(queue, value); break; case 2: value = dequeue(queue); if (value != -1) { printf("Dequeued value: %d\n", value); } break; case 3: value = peek(queue); if (value != -1) { printf("Front value: %d\n", value); } break; case 4: display(queue); break; case 5: exit(0); default: printf("Invalid choice! Please enter a valid option.\n"); } } return 0; // Return 0 to indicate successful execution } 

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the queue.

Structure to Represent a Queue

• The Queue structure contains two pointers, front and rear, which point to the front and rear nodes of the queue, respectively.

Function to Create a New Node

• The newNode function creates a new node with the given value and returns a pointer to it.

Function to Create an Empty Queue

• The createQueue function allocates memory for a new Queue structure and initializes both front and rear to NULL, indicating that the queue is empty.

Function to Check if the Queue is Empty

• The isEmpty function returns 1 if the front of the queue is NULL, indicating the queue is empty, otherwise returns 0.

Function to Enqueue an Element into the Queue

• The enqueue function adds a new node to the rear of the queue. If the queue is empty, the new node becomes both the front and rear of the queue. Otherwise, the new node is added at the end of the queue, and the rear pointer is updated.

Function to Dequeue an Element from the Queue

• The dequeue function removes and returns the front element from the queue if the queue is not empty. If the queue only has one element, both front and rear are reset to NULL after dequeuing.

Function to Peek the Front Element of the Queue

• The peek function returns the front element of the queue without removing it. It is useful for viewing the element at the front of the queue.

Function to Display the Queue Elements

• The display function prints all the elements in the queue from front to rear.

Main Function

• The main function provides a menu-driven interface allowing the user to perform various queue operations interactively.

Output Example

Example Output:

Queue Operations Menu: 1. Enqueue 2. Dequeue 3. Peek 4. Display 5. Exit Enter your choice: 1 Enter value to enqueue: 10 10 enqueued to the queue. Queue Operations Menu: 1. Enqueue 2. Dequeue 3. Peek 4. Display 5. Exit Enter your choice: 1 Enter value to enqueue: 20 20 enqueued to the queue. Queue Operations Menu: 1. Enqueue 2. Dequeue 3. Peek 4. Display 5. Exit Enter your choice: 4 Queue elements: 10 20 Queue Operations Menu: 1. Enqueue 2. Dequeue 3. Peek 4. Display 5. Exit Enter your choice: 2 Dequeued value: 10 

Conclusion

This C program demonstrates how to implement a queue using a linked list. It includes basic queue operations such as enqueue, dequeue, peek, and display, making it a useful example for beginners learning about data structures in C programming.