Circular Queue using Linked List in Java

circular queue using linked list

Implementation of Circular Queue using linked list

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position. 

Why we need circular queue ??

When we work with normal Queue, we can insert elements till queue is full. But when queue is full, we are not allowed to insert the next element this is the problem with normal queue . To overcome this problem circular queue is used .

A circular queue overcomes the problem of unused space in normal queues, and it can be implemented on both arrays and linked list.

                                                                                Operation In Circular Queue:

The following are the operations that can be performed on a circular queue:

  • Front: It is used to get the front item from the Queue.
  • Rear: It is used to get the last element from the Queue.
  • enQueue() This operation adds a new node after rear and moves rear to the next node.
  • deQueue() This operation removes the front node and moves front to the next node.

Algorithm for Insertion:

  • START

static void enQueue(Queue q, int d)

    { 
        Node tp = new Node(); 
        tp.data =d;     
        if (q.front == null) 
            q.front = tp; 
        else
            q.rear.next = tp; 

 

        q.rear = tp; 
        q.rear.next = q.front; 
    } 
  • END

Algorithm for Deletion:

  • START
static int deQueue(Queue q) 
    { 
        if (q.front == null) { 
            System.out.print(“empty queue”); 
            
        } 

 

        
        int d;
        if (q.front == q.rear) 
        { 
         d=q.front.data; 
            q.front = null; 
            q.rear = null; 
        } 
        else 
        { 
            Node tp = q.front; 
             d=tp.data; 
            q.front = q.front.next; 
            q.rear.next = q.front; 
        } 

 

        return d
        }
  • END

Java code :


import java.util.*; 

class prepinsta { 

    
    class Node { 
        int data
        Node next
    } 

     class Queue { 
        Node frontrear
    } 

    
    static void enQueue(Queue qint d)
    { 
        Node tp = new Node(); 
        tp.data =d;     
        if (q.front == null
            q.front = tp; 
        else
            q.rear.next = tp; 

        q.rear = tp; 
        q.rear.next = q.front
    } 

    
    static int deQueue(Queue q
    { 
        if (q.front == null) { 
            System.out.print(“empty queue”); 
            
        } 

        
        int d;
        if (q.front == q.rear
        { 
         d=q.front.data
            q.front = null
            q.rear = null
        } 
        else 
        { 
            Node tp = q.front
             d=tp.data
            q.front = q.front.next
            q.rear.next = q.front
        } 

        return d
        }
    

    // Function displaying the elements 
    static void displayQueue(Queue q
    { 
        Node tp = q.front
        System.out.print(“Elements in Circular Queue are: “); 
        while (tp.next != q.front) { 
            System.out.printtp.data); 
            tp = tp.next
        } 
        System.out.print(tp.data); 
    } 

    
    public static void main(String args[]) 
    { 
        // Creating a queue 
        Queue q = new Queue(); 
        q.front = q.rear = null

        // Inserting elements in Circular Queue 
        enQueue(q, 20); 
        enQueue(q, 40); 
        enQueue(q, 60); 

        // Display elements 
        displayQueue(q); 

        // Deleting elements 
        System.out.print(DeletedeQueue(q)); 
        System.out.print(DeletedeQueue(q)); 
        System.out.println(“AFTER DELETING ELEMENT ELEMENT LEFT  “); 
        // Remaining elements in Circular Queue 
        displayQueue(q); 
        System.out.println(“AFTER INSERTING NEW VALUE “); 
        enQueue(q, 80); 
        displayQueue(q); 
    } 


OUTPUT:

20

40

60

AFTER DELETING ELEMENT ELEMENT LEFT

60

AFTER INSERTING NEW VALUE 

60

80