How to implement Queue using Link List?

DS And Algorithm
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

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

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

Then you have to define 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 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 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 part (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 a conditions if 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 work. Firstly the check a condition that our list is empty or not if empty then print a message that queue is empty. If 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 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


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 Bangla Kings Software as Junior 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 *