Implement Circular Queue using Java

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 to make a circle.

Why use Circular Queue Data Structure

In a normal Queue Data Structure, we can insert elements until queue becomes full. But once if queue becomes full and later if elements are dequeued, we have to shift all the elements every time an element is to be inserted in the queue.

Regular queue operations.

The Queue has a single element with value 15. So both the front and rear point to the same single element-

We now enqueue elements to make the queue full. So the element with value 21 is our rear element while element with value 15 is our first element as follows-

Next Dequeue an element with value 15 from the queue. So our first element will now be element having value 16 as follows-

If elements are now to be added to the queue, space must be made by shifting all the queue elements forward. So all the elements from 16 to 21 are moved forward to create space for our new rear element 22.

So the operations of a normal queue involves shifting of elements during the operations. This can be avoided by making use of Circular Queue.

Circular queue operations.

The circular queue has a single element with value 15. So both the front and rear point to the same single element-

We now enqueue elements to make the circular queue full. So the element with value 22 is our rear element while element with value 15 is our first element as follows-

Next Dequeue an element with value 15 from the circular queue. So our first element will now be element having value 16 as follows-

If a new element is to be added to the circular queue there is no need to shift the existing elements only the rear pointer will need to be moved to the appropriate location as follows-

Circular Queue Program

package com.javainuse;

import java.util.Arrays;

public class CircularQueueImplementation {

    public static void main(String[] args) {

        CircularQueue<Integer> circularQueue = new CircularQueue(8);

        circularQueue.enqueue(15);
        circularQueue.enqueue(16);
        circularQueue.enqueue(17);
        circularQueue.enqueue(18);
        circularQueue.enqueue(19);
        circularQueue.enqueue(20);
        circularQueue.enqueue(21);
        circularQueue.enqueue(22);

        System.out.println("Full Circular Queue" + circularQueue);

        System.out.print("Dequeued following element from circular Queue ");
        System.out.println(circularQueue.dequeue() + " ");
        circularQueue.enqueue(23);
        System.out.println("After enqueueing circular queue with element having value 23");
        System.out.println(circularQueue);
    }

}

//implementation of Circular Queue using Generics
class CircularQueue<E> {

    private int currentSize; //Current Circular Queue Size
    private E[] circularQueueElements;
    private int maxSize; //Circular Queue maximum size

    private int rear;//rear position of Circular queue(new element enqueued at rear).
    private int front; //front position of Circular queue(element will be dequeued from front).      

    public CircularQueue(int maxSize) {
        this.maxSize = maxSize;
        circularQueueElements = (E[]) new Object[this.maxSize];
        currentSize = 0;
        front = -1;
        rear = -1;
    }

    /**
     * Enqueue elements to rear.
     */
    public void enqueue(E item) throws QueueFullException {
        if (isFull()) {
            throw new QueueFullException("Circular Queue is full. Element cannot be added");
        }
        else {
            rear = (rear + 1) % circularQueueElements.length;
            circularQueueElements[rear] = item;
            currentSize++;
            
            if (front == -1) {
				front = rear;
			}
        }
    }

    /**
     * Dequeue element from Front.
     */
    public E dequeue() throws QueueEmptyException {
        E deQueuedElement;
        if (isEmpty()) {
            throw new QueueEmptyException("Circular Queue is empty. Element cannot be retrieved");
        }
        else {
            deQueuedElement = circularQueueElements[front];
            circularQueueElements[front] = null;
            front = (front + 1) % circularQueueElements.length;
            currentSize--;
        }
        return deQueuedElement;
    }

    /**
     * Check if queue is full.
     */
    public boolean isFull() {
        return (currentSize == circularQueueElements.length);
    }

    /**
     * Check if Queue is empty.
     */
    public boolean isEmpty() {
        return (currentSize == 0);
    }

    @Override
    public String toString() {
        return "CircularQueue [" + Arrays.toString(circularQueueElements) + "]";
    }

}

class QueueFullException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public QueueFullException() {
        super();
    }

    public QueueFullException(String message) {
        super(message);
    }

}

class QueueEmptyException extends RuntimeException {

    private static final long serialVersionUID = 1L;

    public QueueEmptyException() {
        super();
    }

    public QueueEmptyException(String message) {
        super(message);
    }

}

Download Source Code

Download it - Circular Queue implementation using Java

			See Also
		
Overriding equals() in Java
Internal working of ConcurrentHashMap in Java
Image Comparison in Java
Java - PermGen space vs Heap space
Java - PermGen space vs MetaSpace
Java 8 Features
Java Miscelleneous Topics
Java Basic Topics
Java- Main Menu
Top Java Data Structures and Algorithm Interview Questions