coder7777 coder7777 - 3 years ago 78
Java Question

Not understanding code for queue implementation

I'm having difficulty understanding some part of the queue implementation in java. I need help understanding the code. I'm relatively new to programming. This is not my code. It will be helpful if somebody explains with a small example.

In the

enqueue
method, what does
rear == capacity - 1
condition doing?

In the
dequeue
method, what does
front == capacity - 1
condition doing?

public class QueueImpl {

private int capacity;
int queueArr[];
int front = 0;
int rear = -1;
int currentSize = 0;

public QueueImpl(int queueSize){
this.capacity = queueSize;
queueArr = new int[this.capacity];
}

/**
* this method adds element at the end of the queue.
* @param item
*/
public void enqueue(int item) {
if (isQueueFull()) {
System.out.println("Overflow ! Unable to add element: "+item);
} else {
rear++;
if(rear == capacity-1){
rear = 0;
}
queueArr[rear] = item;
currentSize++;
System.out.println("Element " + item+ " is pushed to Queue !");
}
}

/**
* this method removes an element from the top of the queue
*/
public void dequeue() {
if (isQueueEmpty()) {
System.out.println("Underflow ! Unable to remove element from Queue");
} else {
front++;
if(front == capacity-1){
System.out.println("Pop operation done ! removed: "+queueArr[front-1]);
front = 0;
} else {
System.out.println("Pop operation done ! removed: "+queueArr[front-1]);
}
currentSize--;
}
}

/**
* This method checks whether the queue is full or not
* @return boolean
*/
public boolean isQueueFull(){
boolean status = false;
if (currentSize == capacity){
status = true;
}
return status;
}

/**
* This method checks whether the queue is empty or not
* @return
*/
public boolean isQueueEmpty(){
boolean status = false;
if (currentSize == 0){
status = true;
}
return status;
}
}

Answer Source

Try to visualize how the items are stored in the internal queueArr[] array. It is not how you would do it naive, however let us first take a look at this concept.


In a naive concept you store the first element of the queue at queueArr[0], the second at queueArr[1], the last element at queueArr[queueArr.length - 1] and so on.

However what would you do if a new element comes or if one should be removed? Then you either need to create a new array with a greater capacity and copy everything to the new array or you have gaps in between.


Your queue implementation has a better concept, it stores the elements cyclical in the array.

Imagine you have a full array. Then you remove the first element, the first slot queueArr[0] is now empty. Now you want to insert a new element at the end. You will now insert it at queueArr[0] and reuse that empty space.

As the meaning of where your data-structure starts and ends is now variable you need to memorize that with a rear and front variable.

Here is an image a small Google search yield that demonstrates this technique:

Queue Cyclic Array


The conditions rear == capacity - 1 and front == capacity - 1 now exactly handle that case I described above. If the array is full but has a gap in the beginning indices, then you insert new elements there, therefore the rear of the array is at the beginning indices. In the example above where rear was first at queueArr.length - 1, it is at 0 afterwards.

In detail:
rear == capacity - 1 resolves to true once the rear pointer is at the right end of the array (note that capacity is the same as queueArr.length).
If it resolved to true then your code executes rear = 0; which sets the pointer back to the beginning of the array. Thus it wanders from left to right and then back to left through the array.

Analogously for the front pointer.


Note that the concept is efficient only because a queue does not allow deletion or insertion in between, you can only change something at the beginning or at the end. Otherwise the internal data would not be connected anymore.

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