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.

Top Blogs
C Functions ! What is a Function Published at:- Types of Function in C ! Library Function in C ! User Defined Function In C ! Function Definition Published at:- Functions that return multiple values -C Example Published at:- Functions with arguments and return values -C Examples Published at:- Functions with arguments and no return values. Published at:- Example of Function with no return type and no argument Published at:- Loops in C Published at:- Structure in C: Introduction Published at:- C Memory Management ! Dynamic memory allocation Published at:- Learn C Programming language with example Published at:- C Interview Questions And Answers Published at:- What values are printed when we run following? Published at:- C Program example: Input a number and print sum of its digits Published at:- Pointer declaration in C ,Address operator Published at:- C Language Interview Question and Answers Published at:- Benefits of C language over other programming languages Published at:- History of C Language : Introduction to C Programming Language Published at:- How does C Programming Language Work Published at:- Importance of C Programming Language Published at:- Input and Output Functions in C Published at:- Introduction to Implementation of Queue using Linked List Published at:- First C Program Published at:- Inception Of C Language Tutorial for Beginners Published at:- The C Compiler work in C language and its important Published at:- Program Structure with “Hello World” Example Published at:- C Programming Interview Questions Set 1 Published at:- C Programming Interview Questions Set 2 Published at:- C Programming Interview Questions Set 3 Published at:- C Programming Interview Questions Set 4 Published at:- C Programming Interview Questions Set 5 Published at:- C Programming Interview Questions Set 6 Published at:-
R4Rin Team
The content on R4Rin.com website is created by expert teams.