Circular Queue based on Linked List in Java

A circular queue is a linear data structure  which is similar to a queue data structure, but differs in the way that, in a circular queue, the last element is connected with the first element.

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

Write a program in Java to implement circular queue using a linked list with the following operations:

  • Push: To insert an element from the rear end of the circular queue.
  • Pop: To remove an element from the front end of the circular queue.
  • Display: To display the elements currently stored in the circular queue.
import java.io.*;
class Node{
    int data;
    Node next;
    public Node(){
        data = 0;
        next = null;
    }
    public Node(int d){
        data = d;
        next = null;
    }
}
class CircularQueueLinkedList{
    Node front;
    Node rear;
    public CircularQueueLinkedList(){
        front = null;
        rear = null;
    }
    public void push(int d){
        Node n = new Node(d);
        if(front == null)
            front = n;
        else
            rear.next = n;
        rear = n;
        rear.next = front;
        System.out.println(d + " pushed.");
    }
    public void pop(){
        if(front == null){
            System.out.println("Queue underflow!");
            return;
        }
        int d = 0;
        d = front.data;
        if(front == rear){
            front = null;
            rear = null;
        }
        else{
            front = front.next;
            rear.next = front;
        }
        System.out.println(d + " popped.");
    }
    public void display(){
        if(front == null){
            System.out.println("Queue is empty!");
            return;
        }
        Node n = front;
        System.out.println("Circular queue contents:");
        while(n.next != front){
            System.out.print(n.data + "\t");
            n = n.next;
        }
        System.out.println(n.data);
    }
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        CircularQueueLinkedList queue = new CircularQueueLinkedList();
        while(true){
            System.out.println("1. Push");
            System.out.println("2. Pop");
            System.out.println("3. Display");
            System.out.print("Enter your choice: ");
            int choice = Integer.parseInt(br.readLine());
            switch(choice){
                case 1:
                System.out.print("Element to be pushed: ");
                int d = Integer.parseInt(br.readLine());
                queue.push(d);
                break;
                case 2:
                queue.pop();
                break;
                case 3:
                queue.display();
                break;
                default:
                System.out.println("Bye...");
                return;
            }
        }
    }
}

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.