Queue using Linked List in C - Coding

Queue is a linear data structure that follows the First-In-First-Out (FIFO) order of operations. This means the first element added to the queue will be the first one to be removed. There are different ways using which we can implement a queue data structure in C.

In this article, we will learn how to implement a queue using a linked list in C, its basic operations along with their time and space complexity analysis, and the benefits of a linked list queue in C.

Linked List Implementation of Queue in C

A queue is generally implemented using an array, but the limitation of this kind of queue is that the memory occupied by the array is fixed no matter how many elements are in the queue. In the queue implemented using a linked list, the size occupied by the linked list will be equal to the number of elements in the queue. Moreover, its size is dynamic, meaning that the size will change automatically according to the elements present.

Queue in C

Representation of Linked Queue in C

In C, the queue that is implemented using a linked list can be represented by pointers to both the front and rear nodes of the linked list. Each node in that linked list represents an element of the queue. The type of linked list here is a singly linked list in which each node consists of a data field and the next pointer.

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

Basic Operations of Linked List Queue in C

Following are the basic operations of the queue data structure that help us manipulate the data structure as needed:

Operation	Description	Time Complexity	Space Complexity
isEmpty	Returns true if the queue is empty, false otherwise.	O(1)	O(1)
Enqueue	This operation is used to add/insert data into the queue.	O(1)	O(1)
Dequeue	This operation is used to delete/remove data from the queue.	O(1)	O(1)
Peek	This operation returns the front element in the queue.	O(1)	O(1)

Let’s see how these operations are implemented in the queue.

Enqueue Function

The enqueue function will add a new element to the queue. To maintain the time and space complexity of O(1), we will insert the new element at the end of the linked list. The element at the front will be the element that was inserted first.

We need to check for queue overflow (when we try to enqueue into a full queue).

Algorithm for Enqueue Function

Following is the algorithm for the enqueue function:

Create a new node with the given data.
If the queue is empty, set the front and rear to the new node.
Else, set the next of the rear to the new node and update the rear.

Dequeue Function

The dequeue function will remove the front element from the queue. The front element is the one that was inserted first, and it will be present at the front of the linked list.

We need to check for queue underflow (when we try to dequeue from an empty queue).

Algorithm for Dequeue Function

Following is the algorithm for the dequeue function:

Check if the queue is empty.
If not empty, store the front node in a temporary variable.
Update the front pointer to the next node.
Free the temporary node.
If the queue becomes empty, update the rear to NULL.

Peek Function

The peek function will return the front element of the queue if the queue is not empty. The front element is the one at the front of the linked list.

Algorithm for Peek Function

The following is the algorithm for the peek function:

Check if the queue is empty.
If empty, return -1.
Else, return the front->data.

IsEmpty Function

The isEmpty function will check if the queue is empty or not. This function returns true if the queue is empty; otherwise, it returns false.

Algorithm of isEmpty Function

The following is the algorithm for the isEmpty function:

Check if the front pointer of the queue is NULL.
If NULL, return true, indicating the queue is empty.
Otherwise, return false, indicating the queue is not empty.

C Program to Implement a Queue Using Linked List

The below example demonstrates how to implement a queue using a linked list in C.

// C program to implement queue using linked list

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

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

// Define the structure for the queue
typedef struct Queue {
    node* front;
    node* rear;
} queue;

// Function to create a new node
node* createNode(int data)
{
    // Allocate memory for a new node
    node* newNode = (node*)malloc(sizeof(node));
    // Check if memory allocation was successful
    if (newNode == NULL)
        return NULL;
    // Initialize the node's data and next pointer
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to create a new queue
queue* createQueue()
{
    // Allocate memory for a new queue
    queue* newQueue = (queue*)malloc(sizeof(queue));
    // Initialize the front and rear pointers of the queue
    newQueue->front = newQueue->rear = NULL;
    return newQueue;
}

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

// Function to add an element to the queue
void enqueue(queue* q, int data)
{
    // Create a new node with the given data
    node* newNode = createNode(data);
    // Check if memory allocation for the new node was
    // successful
    if (!newNode) {
        printf("Queue Overflow!\n");
        return;
    }
    // If the queue is empty, set the front and rear
    // pointers to the new node
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    // Add the new node at the end of the queue and update
    // the rear pointer
    q->rear->next = newNode;
    q->rear = newNode;
}

// Function to remove an element from the queue
int dequeue(queue* q)
{
    // Check if the queue is empty
    if (isEmpty(q)) {
        printf("Queue Underflow\n");
        return -1;
    }
    // Store the front node and update the front pointer
    node* temp = q->front;
    q->front = q->front->next;
    // If the queue becomes empty, update the rear pointer
    if (q->front == NULL)
        q->rear = NULL;
    // Store the data of the front node and free its memory
    int data = temp->data;
    free(temp);
    return data;
}

// Function to return the front element of the queue
int peek(queue* q)
{
    // Check if the queue is empty
    if (isEmpty(q))
        return -1;
    // Return the data of the front node
    return q->front->data;
}

// Function to print the queue
void printQueue(queue* q)
{
    // Traverse the queue and print each element
    node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    // Create a new queue
    queue* q = createQueue();

    // Enqueue elements into the queue
    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);
    enqueue(q, 40);
    enqueue(q, 50);

    // Print the queue
    printf("Queue: ");
    printQueue(q);

    // Dequeue elements from the queue
    dequeue(q);
    dequeue(q);

    // Print the queue after deletion of elements
    printf("Queue: ");
    printQueue(q);

    return 0;
}

Output

Queue: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Queue: 30 -> 40 -> 50 -> NULL

Benefits of Linked List Queue in C

The following are the major benefits of the linked list implementation over the array implementation:

The dynamic memory management of the linked list provides a dynamic size to the queue that changes with the number of elements.
Rarely reaches the condition of queue overflow.

Conclusion

The linked list implementation of the queue shows that even while providing such benefits, it can only be used when we are ready to bear the cost of implementing the linked list also in our C program. However, if we already have a linked list, we should prefer this implementation over the array one.

The following are some articles about the Queue data structure that can improve your understanding of it:

Reffered: https://www.geeksforgeeks.org

C Language

Related
Tarjan’s Algorithm in C Language
N Queen Problem Using Branch and Bound in C
Partition Equal Subset Sum in C
Shortest Path Algorithm in C
Graph Cycle Detection in C

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	19