Implementation of Queue using Linked List

Introduction to Implementation of Queue using Linked List

A queue is a linear data structure that follows the First in, First out principle(FIFO). Queue supports operations like enqueue and dequeue. It can be implemented using an array and linked list. The benefit of implementing a queue using a linked list over arrays is that it allows to grow the queue as per the requirements, i.e., memory can be allocated dynamically.

What is Queue?

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, which means that the element which is inserted first in the queue will be the first one to be removed from the queue. A good example of a queue is a queue of customers purchasing a train ticket, where the customer who comes first will be served first.

A linked queue is shown here:

Operation on Linked Queue

Each node of a linked queue consists of two fields: data and next(storing address of next node). The data field of each node contains the assigned value, and the next points to the node containing the next item in the queue.

A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front pointer stores the address of the first element of the queue, and the rear pointer stores the address of the last element of the queue.

Insertion is performed at the rear end, whereas deletion is performed at the front end of the queue. If front and rear both points to NULL, it signifies that the queue is empty.

The two main operations performed on the linked queue are:

• Insertion
• Deletion

Insertion

Insert operation or insertion on a linked queue adds an element to the end of the queue. The new element which is added becomes the last element of the queue.

Algorithm to perform Insertion on a linked queue:

1. Create a new node pointer.
   ptr = (struct node *) malloc (sizeof(struct node));

2. Now, two conditions arise, i.e., either the queue is empty, or the queue contains at least one element.

3. If the queue is empty, then the new node added will be both front and rear, and the next pointer of front and rear will point to NULL.

4. If the queue contains at least one element, then the condition front == NULL becomes false. So, make the next pointer of rear point to new node ptr and point the rear pointer to the newly created node ptr

Hence, a new node(element) is added to the queue.

C Function

Output

Deletion

Deletion or delete operation on a linked queue removes the element which was first inserted in the queue, i.e., always the first element of the queue is removed.

Steps to perform Deletion on a linked queue:

1. Check if the queue is empty or not.

2. If the queue is empty, i.e., front==NULL, so we just print 'underflow' on the screen and exit.

3. If the queue is not empty, delete the element at which the front pointer is pointing. For deleting a node, copy the node which is pointed by the front pointer into the pointer ptr and make the front pointer point to the front's next node and free the node pointed by the node ptr. This can be done using the following statement:

C Function

Output

Implementation of queue using linked list in C

Implementing a queue using a linked list allows us to grow the queue as per the requirements, i.e., memory can be allocated dynamically.

A queue implemented using a linked list will not change its behavior and will continue to work according to the FIFO principle.

Steps for implementing queue using linked list:

1. Enqueue Function

Enqueue function adds an element to the end of the queue. It takes O(1) time. The last element can be tracked using the rear pointer.

• First, build a new node with given data.
• Check if the queue is empty or not.
• If a queue is empty then, a new node is assigned to the front and rear.
• Else make next of rear as new node and rear as a new node.

2. Dequeue Function

The dequeue function always removes the first element of the queue. It takes O(1) time. For dequeue, the queue must contain at least one element, else underflow conditions will occur.

• Check if queue is empty or not.
• If the queue is empty, then dequeue is not possible.
• Else store front in temp
• And make next of front as the front.
• Delete temp, i.e, free(temp).

3. Print

Print function is used to display the content of the queue. Since we need to iterate over each element of the queue to print it, the time complexity of the print function is O(n), where n = number of nodes in a queue.

• Check if queue contains at least one element or not.
• If the queue is empty print “No elements in the queue.”
• Else, define a node pointer and initialize it with the front.
• Display data of node pointer until the next node pointer becomes NULL.

Code for implementing queue using linked list in C

Output:

Enqueue Operation:

Dequeue Operation:

Here is an Online C Compiler where you can run your C programs.