Introduction to Implementation of Queue using Linked List
Categories: C Programming language C language
Introduction to Implementation of Queue using Linked List
Queue is a linear data structure which follows the First in, First out principle(FIFO). Queue supports operations like enqueue and dequeue. It can be implemented using array and linked list. The benefit of implementing queue using 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.
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. front pointer and 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 linked queue are:
- Insertion
- Deletion
Insertion
Insert operation or insertion on a linked queue adds an element to the end of queue. The new element which is added becomes the last element of the queue.
Algorithm to perform Insertion on a linked queue:
Create a new node pointer.
ptr = (struct node *) malloc (sizeof(struct node));
Now, two conditions arises, i.e, either the queue is empty or queue contains at least one element.
If 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.
*ptr->data = val;
if (front == NULL) {
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
If 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 rear pointer to the newly created node ptr
rear -> next = ptr;
rear = ptr;
Hence, a new node(element) is added to the queue.