Queue implementation using linked list in Java

Queue implementation using linked list in Java

Queue is another famous data structure which allows operating from two ends(front and rear) through head and tail. It works in First In First Out(FIFO) fashion.

Queue data structure is like two ended room which allows entry(enqueue) from one end called as rear and exit (dequeue) from another end called a front...

So to remember , queue always supports insertion from rear-end / tail and deletion called as dequeue happens only from fron end / head.

Let's see how can we implement simple Queue data structure in Java using a single linked list.

We need follow the Cell class we have used in the Stack example in the previous post.

Queue main class :

package com.krish.queue;

import com.krish.datastructures.common.Cell;

public class QueueMain {
 Cell head;
 Cell tail;

 public QueueMain() {
  head = null;
  tail = null;
 }

 public void enqueue(Object obj) {
  Cell newCell = new Cell(obj, null);
  if (head == null && tail == null)
   head = newCell;
  else
   tail.next = newCell;
  tail = newCell;
  System.out.println("Enqueud element:"+obj);
  printQueue();
 }

 public Cell front() {
  return head;
 }

 public Cell rear() {
  return tail;
 }

 public void dequeue() {
  if (head == null && tail == null) {
   System.out.println("Q is empty");
  } else {
   System.out.println("Dequeued element:"+head.getVal());
   if (head.next == null) {
    tail = null;
   }
   head = head.next;
  }
  printQueue();
 }

 public int getsize() {
   int size = 0;
  if(!(head ==null && tail == null)){
     size = 1;
     for(Cell n = head; n.next != null; n = n.next)
         size = size+1; 
  
     return size;
  }
  return size;
  }

 public void printQueue() {
  if (head == null && tail == null) {
   System.out.println("Q is empty");
  } else {
   System.out.println("Q Elememts:");
   Cell current = head;
   System.out.println("Head");
   while (current != null) {
    System.out.println("->" + current.getVal());
    current = current.next;
   }
   System.out.println("<--tail br="">   System.out.println("Size of the Q:"+getsize());
  }
 }

 public static void main(String[] args) {
  QueueMain queue = new QueueMain();
  queue.enqueue(23);
  queue.enqueue(43);
  queue.enqueue(143);
  queue.enqueue(321);
  queue.dequeue();
  queue.dequeue();
 }
}

Output :

Enqueud element:23
Q Elememts:
Head
->23
<--tail br="">Size of the Q:1
Enqueud element:43
Q Elememts:
Head
->23
->43
<--tail br="">Size of the Q:2
Enqueud element:143
Q Elememts:
Head
->23
->43
->143
<--tail br="">Size of the Q:3
Enqueud element:321
Q Elememts:
Head
->23
->43
->143
->321
<--tail br="">Size of the Q:4
Dequeued element:23
Q Elememts:
Head
->43
->143
->321
<--tail br="">Size of the Q:3
Dequeued element:43
Q Elememts:
Head
->143
->321
<--tail br="">Size of the Q:2

References : [1][2][3][4]