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.
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.
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
- Queue introduction and implementation
- Stack Example 1: Reverse a string
- Delimiter matching using stack
- Queue No-count approach and implementation