circular queue

Circular Queue using Array (Wrapping Around)

To understand the concept of Circular Queue (Front and Rear arrows wrap around), consider the Queue Implementation Example and make the following changes.

First comment out the following lines in MyQueue class, Basically what you are doing is commenting out the logic for handling wrap around.

//handling wrap around
//if(rear == maxQueueArraySize-1)
//rear = -1;

And modify your QueueExample class like the following

public class QueueExample {
	
	public static void main (String[] args)
	{
		//create queue using MyQueue that can hold 4 items
		MyQueue myQueue = new MyQueue(5);
		
		//i) Insert 3 elements in the queue
		myQueue.insert(3);
		myQueue.insert(5);
		myQueue.insert(7);			
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());
		
		//ii) Insert an element and remove an element. 
		//call isEmpty()to ensure that there are elements in the queue before calling remove()
		if (!myQueue.isEmpty())
			myQueue.remove();
		//insert an element
		myQueue.insert(9);		
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());		
	
		//iii) Queue with some more items removed.
		if (!myQueue.isEmpty())
			myQueue.remove();		
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());
		
		//iv) Insert an element at rear
		myQueue.insert(10);		
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());
		
		//v) Try to insert one more element when the rear of the queue is at the end of the array (max index)
		myQueue.insert(11);
		
		while (!myQueue.isEmpty())
		{
			long element = myQueue.remove();
			System.out.println(element);
		}		
		
	}

}

Circular Queue using Array

Whenever you insert a new item in the queue, the Front arrow moves upward towards the higher index of the array and whenever you remove an item from the queue, the Rear arrow also moves upward as shown in the following figure.

circular queue
QueueExample class is modified inline with the above operations. Try these operations with Queue Implementation example by commenting wrap around logic as mentioned above. The final code should look like the following

package com.sneppets.dsalgo;

class MyQueue
{
	//max queue array size 
	private int maxQueueArraySize;
	
	//queue array
	private long[] myQueueArray;
	
	//queue front
	private int front;
	
	//queue rear
	private int rear;
	
	//number of elements
	private int nElements;
	
	//constructor
	public MyQueue(int size)
	{
		//set queue array size
		maxQueueArraySize = size;
		//create array
		myQueueArray = new long[maxQueueArraySize];		
		front = 0;		
		rear = -1;		
		//no elements yet in the queue
		nElements = 0;
		
	}
	
	//insert element at rear of the queue
	public void insert(long element)
	{
		//handling wraparound
		//if(rear == maxQueueArraySize-1)
		//	rear = -1;
		
		//increment rear and insert element
		myQueueArray[++rear] = element;
		
		//added one more element in the Queue
		nElements++;
		
	}
	
	//remove element from front of the Queue.
	public long remove()
	{
		long temp = myQueueArray[front++];
		if(front == maxQueueArraySize)
			front = 0;
		//less by one element
		nElements--;
		
		return temp;		
	}
	
	//to peek at front of the queue
	public long peekFront()
	{
		return myQueueArray[front];
	}
	
	//to peek at front of the queue
	public long peekRear()
	{
		return myQueueArray[rear];
	}
	
	//return true if queue is empty
	public boolean isEmpty()
	{
		return (nElements==0);
	}
	
	//return true is queue is full
	public boolean isFull()
	{
		return (nElements==maxQueueArraySize);
	}
	
	//return number of elements in the Queue
	public int size()
	{
		return nElements;
	}
	
}

/**
 * 
 * @author sneppets.com
 *
 */
public class QueueExample {
	
	public static void main (String[] args)
	{
		//create queue using MyQueue that can hold 4 items
		MyQueue myQueue = new MyQueue(5);
		
		//i) Insert 3 elements in the queue
		myQueue.insert(3);
		myQueue.insert(5);
		myQueue.insert(7);			
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());
		
		//ii) Insert an element and remove an element. 
		//call isEmpty()to ensure that there are elements in the queue before calling remove()
		if (!myQueue.isEmpty())
			myQueue.remove();
		//insert an element
		myQueue.insert(9);		
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());		
	
		//iii) Queue with some more items removed.
		if (!myQueue.isEmpty())
			myQueue.remove();		
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());
		
		//iv) Insert an element at rear
		myQueue.insert(10);		
		System.out.println("Peek Front: " + myQueue.peekFront());
		System.out.println("Peek Rear: " + myQueue.peekRear());
		
		//v) Try to insert one more element when the rear of the queue is at the end of the array (max index)
		myQueue.insert(11);
		
		while (!myQueue.isEmpty())
		{
			long element = myQueue.remove();
			System.out.println(element);
		}		
		
	}

}

The problem with this code or approach is that the rear arrow of the queue has reached the end of the array (maximum index) at step iv. as shown in the figure above.

And when you try to insert another item in step v., even if there are empty cells at the beginning of the array you would see the following error

Peek Front: 3
Peek Rear: 7
Peek Front: 5
Peek Rear: 9
Peek Front: 7
Peek Rear: 9
Peek Front: 7
Peek Rear: 10
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
	at com.sneppets.dsalgo.MyQueue.insert(QueueExample.java:42)
	at com.sneppets.dsalgo.QueueExample.main(QueueExample.java:133)

Wrap Around

To solve the above problem of not being able to insert an item even if the queue is not full, the front and rear arrows of the queue wrap around to the beginning of the array as shown in figure. This is called circular queue or ring buffer.

circular queue wrap around

Note that after the rear arrow is wrapped around, it is now below the front arrow i.e., the reverse of the original arrangement.

With wrap around logic when you run the above program you should be able to insert more items and see the following output

Peek Front: 3
Peek Rear: 7
Peek Front: 5
Peek Rear: 9
Peek Front: 7
Peek Rear: 9
Peek Front: 7
Peek Rear: 10
7
9
10
11

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of