Circular Queue implementation in Java using array. 3

Queue is an abstract data type which support below operation.

  1. new() – > for making new Queue.
  2. enqueue() – > insert element at rear.
  3. dequeue() – > remove an element from front.

Supporting methods will be :

  1. size()
  2. isEmpty()
  3. isFull()

Let’s start implementation of Queue via circular array.
Below is the circular array:

In queue we will be maintain two pointer front and rear. Front will point to the first element i.e. head of the queue and dequeue operation will be happened from front pointer. Rear pointer will point at the last element and enqueue will happen at rear pointer.

Now first start writing the pseudo code.

Operation:

Below f denotes front pointer and r denotes rear pointer.

 

full() - >  if( r – f == -1 || N -1) then // N is the initial capacity of the array. In above figure the size is 9
                  return true
              else
                  return false

empty() - > if (r == f) then 
                        return true

size() - > if (r > f) then
                   return r – f 
                else
                   N – f + r 

enqueue() - > if(isFull()) then
                             throw QueueFullException
                          else
                             Q[r] < - object
                             r < - (r + 1) mod N  // this is because of circular array. N is initial capacity

dequeue() - > if(isEmpty()) then
                             throw QueueEmptyException
                         else
                            Q[f] < - null
                            f < - (f + 1) mod N 

Now Lets start implementing it in Java

package com.algo.queue;

public interface Queue {
	
	// return the size of the queue
	public int size();
	
	public boolean isEmpty();
	
	public boolean isFull();
	
	// insert an element into the queue 
	public void enqueue(Object obj) throws QueueFullException;
	
	// removes an element from the queue 
	public Object dequeue() throws QueueEmptyException;	

}

Now lets define class QueueFullException and QueueEmptyException


package com.algo.queue;

public class QueueFullException extends RuntimeException {

	public QueueFullException(){
		super();
	}
	
	public QueueFullException(String message){
		super(message);
	}
	
	public QueueFullException(String message, Throwable cause){
		super(message, cause);
	}
}

package com.algo.queue;

public class QueueEmptyException extends RuntimeException {

	public QueueEmptyException(){
		super();
	}
	
	public QueueEmptyException(String message){
		super(message);
	}
	
	public QueueEmptyException(String message, Throwable cause){
		super(message, cause);
	}
}

Now lets implement Queue interface :


package com.algo.queue;

public class CircularArrayQueue implements Queue{
	
	private static final int capacity = 5;
	private Object[] Q;
	private final int N; // capacity
	private int f = 0;
	private int r = 0;

	
	public CircularArrayQueue(){
		this(capacity);
	}
	
	public CircularArrayQueue(int capacity){
		N = capacity;
		Q = new Object[N];
	}

	public int size() {
        if(r > f)
        	return r - f;
        return N - f + r;
	}

	public boolean isEmpty() {
		return (r == f) ? true : false;
	}

	public boolean isFull() {
        int diff = r - f; 
		if(diff == -1 || diff == (N -1))
			return true;
		return false;
	}

	public void enqueue(Object obj) throws QueueFullException {
		if(isFull()){
			throw new QueueFullException("Queue is Full.");
		}else{
			Q[r] = obj;
			r = (r + 1) % N;
		}
	}

	public Object dequeue() throws QueueEmptyException {
		Object item; 
		if(isEmpty()){
			throw new QueueEmptyException();
		}else{
			item = Q[f];
			Q[f] = null;
			f = (f + 1) % N;
		}
       return item;
	}

}

Now Lets test it:


package com.algo.queue;

public class RunQueue {

	public static void main(String[] args) {
		Queue queue = new CircularArrayQueue();
		
		queue.enqueue("A");
		queue.enqueue("B");
		queue.enqueue("C");
		queue.enqueue("D");
		//queue.enqueue("E");
		System.out.println(queue.size());
		System.out.println(queue.dequeue());
		queue.enqueue("E");
		System.out.println(queue.size());
		//queue.enqueue("F");
		System.out.println(queue.dequeue());
		System.out.println(queue.size());
	}
	
}

3 thoughts on “Circular Queue implementation in Java using array.

  1. Reply Lucie@Identification Theft Aug 19,2013 11:34 am

    Way cool! Some very valid points! I appreciate you penning
    this write-up plus the rest of the site is really good.

  2. Reply Sanjeet Suhag Dec 31,2013 6:32 am

    Thank you so much. I’m a student and I’ve been looking all over the internet for a proper explanation of a in .

  3. Reply standy Feb 23,2015 3:59 pm

    Youre so cool! I dont suppose Ive read something like this before. So nice to seek out any person with some authentic ideas on this subject. realy thanks for beginning this up. this web site is one thing that’s needed on the net, someone with slightly originality. useful job for bringing something new to the internet!

Leave a Reply