Implementation of Queues using Linked List in Java

July 12, 2022

Let us see how to Implement Queue using linked list in java ?

As we know that array implementation can not be used for the many large values where the queues are implemented. So that’s why as an alternative array implementation of queue is replaced by linked link implementation of queue.

Implementing queues using link list will increase the efficiency of the program .

Basic Operations of Queue

Enqueue: When we want to add an element to the end of the queue
Dequeue: when we want to Remove an element from the front of the queue
IsEmpty: Check if the queue is empty
IsFull: Check if the queue is full
Peek: Get the value of the front of the queue without removing it

ALGORITHMS:

ENQUEUE:

public void enqueue(int data)

{

Node old = rear;

rear = new Node();

rear.data = data;

rear.next = null;

if (isEmpty())

{

front = rear;

}

else

{

old.next = rear;

}

s++;

System.out.println(data+ ” added to the queue”);

}

DEQUEUE:

public int dequeue()

{

int data = front.data;

front = front.next;

if (isEmpty())

{

rear = null;

}

s–;

System.out.println(data+ ” removed from the queue”);

return data;

}

JAVA CODE TO IMPLEMENT QUEUE USING LINK LIST .

Run

public class Main
{
     private Node front, rear; 
     private int s; // number of items
     
     //class to define linked node
     private class Node
     { 
     int data;
     Node next;
     }
     
     
     public Main()
     {
         front = null;
         rear = null;
         s = 0;
     }
     
     public boolean isEmpty()
     {
        return (s == 0);
     }
     
     //to Remove item 
     public int dequeue()
     {
         int data = front.data;
         front = front.next;
         if (isEmpty()) 
         {
            rear = null;
         }
         s--;
         System.out.println(data+ " removed from the queue");
         return data;
     }
     
     //to Add data .
     public void enqueue(int data)
     {
         Node old = rear;
         rear = new Node();
         rear.data = data;
         rear.next = null;
         if (isEmpty()) 
         {
            front = rear;
         }
         else 
         {
            old.next = rear;
         }
             s++;
             System.out.println(data+ " added to the queue");
     }
     
     public static void main(String args[]){
         
         Main queue = new Main();
         queue.enqueue(1);
         queue.dequeue();
         queue.enqueue(2);
         queue.enqueue(3);
         queue.enqueue(4);
         queue.dequeue();
         queue.enqueue(5);
         queue.dequeue();
         queue.enqueue(6);
         queue.enqueue(7);
         queue.dequeue();
         queue.enqueue(8);
         queue.enqueue(9);
     }
}

OUTPUT:

1 added to the queue
1 removed from the queue
2 added to the queue
3 added to the queue
4 added to the queue
2 removed from the queue
5 added to the queue
3 removed from the queue
6 added to the queue
7 added to the queue
4 removed from the queue
8 added to the queue
9 added to the queue