How to implement Queue using Link List?

queue-link-list
Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Hello Programmer,

How are you doing? In this tutorial, I will show you how to implement Queue using the Link list. Prerequisite: You have to know What is the link list? How does It work? And algorithm of Queue. Well, I assume you are familiar with those prerequisites. Implement Queue using Array

How to implement Queue using Link List?

Well, Implement the Queue in the link list, first, you’ve to define a structure that has two-part, one is the data part another one is the address part. (address of next node).

Queue using Link List
Queue using Link List
typedef struct Node{
    int data;
    struct Node *next;
}node;

Then you have to define a two-pointer variable.

node *front,*rear;

Then initialize a function where define front = rear = 0

void initial(){
    front = rear = 0;
}

Well, Our initial setup has been done, Now implement the enqueue function.

void enqueue(int val){
    node *newNode;
    newNode = new node;
    newNode->data = val;
    newNode->next = 0;
    if(front == 0 && rear == 0){
        front = rear =  newNode;
    }else{
        rear->next = newNode;
        rear = rear->next;
    }
}

Let me explain how enqueue function works. Here you can see the first line of enqueue function I declare a pointer which data type is according to the structure. Well, then using new operator initializes the memory and returns the address of the newly allocated and initialized memory to the pointer variable. Check Our structure where I have defined two parts (data and address part) , so in this data part, I store data which is I sent using enqueue function’s parameter. Then address part I stored 0(NULL). Then check conditions if the front and rear == 0 front and rear value would be newNode which is created firstly in enqueue function, then else part the address part of rear = newNode, and rear equal to next address of rear.

dequeue function :

int dequeue(){
    if(front == 0 && rear == 0){
        cout<<"\nEmpty Queue!\n";
        return -9999;
    }
    int data = front->data;
    node *temp = front;
    front = front->next;
    free(temp);
    return data;
}

Let me explain how dequeue function is works. Firstly the check a condition that our list is empty or not if empty then print a message that queue is empty. If the queue isn’t empty then define a integer value for our data then define a temporary node variable then move our root pointer then we have to free the temporary variable and finally return our data.

display the values using display function :

void display(node *top){
    node *temp = top;
    if(top == 0){
        cout<<"\nEmpty Queue!\n";
        return;
    }
    while(temp != 0){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

In this display function first we declare a node variable then assign with our top pointer. then check a condition, if top equal to zero or NULL print that our queue is empty. If queue isn’t empty then define a while loop which is execute top to NULL , inside the loop we print our value.

Source code : https://github.com/AR-Shahin/Data_Structure_and_Algorithm/blob/main/Queue/Queue_using_link_list.txt

Read More : Implement a Binary tree with inOrder postOrder preOrder

Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  

About Anisur Rahman Shahin

Hello. My name is Shahin. I'm a tech enthusiast guy. Personally, I’m Optimistic and always in hurry kinda person. I'm a freelance web developer. I am working at Zakir Soft as Laravel Developer. My Portfolio website: https://devshahin.com/

View all posts by Anisur Rahman Shahin →

Leave a Reply

Your email address will not be published. Required fields are marked *