Raghu Raghu -3 years ago 112
Java Question

Java Queue's isFull method implementation without nitems field

I going through a java algorithms book. One of the ways of implementing a queue is with out using nitems field to check if the queue is empty or full. Following is the method that I am trying to wrap my head around. I tried understanding this by drawing arrays on white board etc. with no clear understanding.

Can any one of you please shed some light on the code below ? Appreciate you taking time to look at this.

public boolean isFull() // true if queue is full
{
return ( rear+2==front || (front+maxSize-2==rear) );
}


Additional notes:

In this style of implementation of a queue with out nelems, the size of the array i.e "maxSize" is (queuesize+1) e.g. for a queue size of 5 elements, maxSize will be 6. Additional array element is used to resolve a situation where queue appears to be empty and full at the same time.

Where "rear" field is the position on the array and it gets updated when ever a new element is inserted into the queue as queues are FIFO. "front will not be updated when a new element is inserted.

"front" field is the position of the first element in the queue i.e. the element that will be popped of the queue up on calling a remove method.

Below is the complete Algorithm from the book in case my explanation is not clear. I think I understood isEmpty method, however isFull method is not whats clear to me.

class Queue
{
private int maxSize;
private long[] queArray;
private int front;
private int rear;
//--------------------------------------------------------------
public Queue(int s) // constructor
{
maxSize = s+1; // array is 1 cell larger
queArray = new long[maxSize]; // than requested
front = 0;
rear = -1;
}
//--------------------------------------------------------------
public void insert(long j) // put item at rear of queue
{
if(rear == maxSize-1)
rear = -1;
queArray[++rear] = j;
}
//--------------------------------------------------------------
public long remove() // take item from front of queue
{
long temp = queArray[front++];
if(front == maxSize)
front = 0;
return temp;
}
//--------------------------------------------------------------
public long peek() // peek at front of queue
{
return queArray[front];
}
//--------------------------------------------------------------
public boolean isEmpty() // true if queue is empty
{
return ( rear+1==front || (front+maxSize-1==rear) );
}
//--------------------------------------------------------------
public boolean isFull() // true if queue is full
{
return ( rear+2==front || (front+maxSize-2==rear) );
}
//--------------------------------------------------------------
public int size() // (assumes queue not empty)
{
if(rear >= front) // contiguous sequence
return rear-front+1;
else // broken sequence
return (maxSize-front) + (rear+1);
}
//--------------------------------------------------------------
} //


Thanks!

Raghu

Answer Source

The best way to visualize this implementation is to write down a test case and look at it. Let's assume we have a queue of 4:

  • front=0
  • rear=-1
  • s=4
  • maxSize=5
  • queArray is an array with indexes 0 through 4.

Since this implementation is a wrap-around of the array, you can have rear in an index ahead of front or front ahead of rear. This is why both isEmpty() and isFull() have two cases. I'll demonstrate it with two example - one where we fill in the array with 4 inserts, and the other with 2 inserts, 1 remove, 3 inserts, 1 remove and 1 insert. Let q be queArray, r be rear and f be front:

  • q=[0,0,0,0,0] f=0 r=-1

    This is the starting position. At this point, before the inserts, the queue is empty - you can use isEmpty() and the condition rear+1==front works, since -1+1==0.

  • q=[5,0,0,0,0] f=0 r=0

    The first insert brings the rear up to 0.

  • q=[5,4,0,0,0] f=0 r=1

    second insert brings the rear to 1.

  • q=[5,4,3,0,0] f=0 r=2

  • q=[5,4,3,2,0] f=0 r=3

Note that at this point the queue is full - it contains 4 elements. calling isFull() you'll see that the condition front+maxSize-2==rear is true: 0+5-2==3.

Now let's try the wrap-around approach, where rear gets to an index behind front. Let's start from the second insert:

  • q=[5,4,0,0,0] f=0 r=1

  • q=[0,4,0,0,0] f=1 r=1

    The first remove. for the sake of the example I actually removed the '5' from the array back to '0' - it actually does not happen in this implementation, the '5' is there but will be overwritten when needed. But for the visualization is works.

  • q=[0,4,3,0,0] f=1 r=2

  • q=[0,4,3,2,0] f=1 r=3
  • q=[0,4,3,2,1] f=1 r=4
  • q=[0,0,3,2,1] f=2 r=4
  • q=[5,0,3,2,1] f=2 r=0

    At this moment we finally wrapped over - the rear is behind front, and we have four elements in the queue! now see that the other condition of isFull() exists: rear+2==front as 0+2==2.

I hope this helped illustrate how the solution works without actually keeping a count of the elements.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download