Implementation of Queues using Linked List in Java

January 20, 2021

implementation of queues using link list

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 .


public class prepinsta
{
 private Node front, rear; 
 private int s; // number of items
 
 //class to define linked node
 private class Node
 { 
 int data;
 Node next;
 }
 
 
 public prepinsta()
 {
 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[]){
 
 prepinsta queue = new prepinsta();
 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