CC-3 : FIFO Circular Queue Using array.

Description:

Create a FIFO Circular Queue using array for storage.

Test cases and expected outputs:

Input Parameters	Expected outputs
QueueCircularArray queue=new QueueCircularArray() queue.add(9); queue.add(14); queue.add(17); queue.add(34); queue.add(21);	Queue nodes: 9 <- 14 <- 17 <- 34 <- 21
queue.remove(); queue.remove(); queue.remove();	Queue nodes: 34 <- 21 <- 28
queue.add(55); queue.add(63);	Queue nodes: 34 <- 21 <- 28<- 55 <- 33

Pseudocode:

The FIFO Array Circular Queue will use a fixed size array for storing data elements.

Maintain pointers to index of first and last data elements in the storage array.

The add() method:

Check if storage array is full, if so, return false.

If array is empty, increment firstIdx and lastIdx.

If lastIdx is greater than Queue size, then set lastIdx to 0; this is because we are using the array as a circular array.

Store new data at index lastIdx.

The remove() method:

If storage array is empty, return false.

If set variable removedData to data element at index firstIdx.

If Queue data element count is 1, Set firstIdx and lastIdx to -1 as the Queue will be empty after current operation.

Else if Queue size > 1, increment firstIdx to 0; this is because we are using the array as a circular array.

Return removedData.

Code:

public class QueueCircularArray {

private int qSize=5;
private int[] queue=new int[qSize];	
private int firstIdx=-1;
private int lastIdx=-1;
	
public int get() {
	if (firstIdx != -1) {
		return queue[firstIdx];
	}
	return Integer.MIN_VALUE;
}

public boolean add(int data){
	if (getSize()==qSize) {return false;}
	if (firstIdx==-1) {firstIdx++;}
	lastIdx++;
	if (lastIdx >= qSize) {lastIdx=0;}
	queue[lastIdx]=data;
	return true;
}

public int remove() {
	if (lastIdx == -1) {return Integer.MIN_VALUE;}
	int removedData=queue[firstIdx];
	if (getSize()==1) {
		queue[firstIdx]=0;
		firstIdx=-1;
		lastIdx=-1;
		return removedData;
	} 
	queue[firstIdx]=0;
	firstIdx++;
	if (firstIdx >= qSize) {firstIdx=0;}
	return removedData;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class QueueCircularArray {

private int qSize=5;
private int[] queue=new int[qSize];	
private int firstIdx=-1;
private int lastIdx=-1;
	
public int get() {
	if (firstIdx != -1) {
		return queue[firstIdx];
	}
	return Integer.MIN_VALUE;
}

public boolean add(int data){
	if (getSize()==qSize) {return false;}
	if (firstIdx==-1) {firstIdx++;}
	lastIdx++;
	if (lastIdx >= qSize) {lastIdx=0;}
	queue[lastIdx]=data;
	return true;
}

public int remove() {
	if (lastIdx == -1) {return Integer.MIN_VALUE;}
	int removedData=queue[firstIdx];
	if (getSize()==1) {
		queue[firstIdx]=0;
		firstIdx=-1;
		lastIdx=-1;
		return removedData;
	} 
	queue[firstIdx]=0;
	firstIdx++;
	if (firstIdx >= qSize) {firstIdx=0;}
	return removedData;
}

public int getSize() {
	if (firstIdx == -1) {return 0;}
	if (firstIdx==0) {return lastIdx+1;}
	if(lastIdx >= firstIdx) {
		return lastIdx-firstIdx+1;
	}else {
		return (qSize-firstIdx)+(lastIdx+1);
	}
}

public void traverse() {
	if (firstIdx == -1) {return;}
	int currIdx=firstIdx;
	do {
			System.out.print(queue[currIdx]);
			System.out.print(",");
			currIdx++;	
			if ((currIdx >= qSize)&& (lastIdx < firstIdx)) {currIdx=0;}
	} while(currIdx != lastIdx+1);
}			

public void printQueue() throws Exception {
	if (firstIdx == -1) {
		System.out.println("\nQUEUE is empty !!");
		return;
	}
   	System.out.println();
	System.out.println("**************************************************");
	System.out.print("Queue Array"+" : ");
	int currIdx=firstIdx;
	do {
			System.out.print(queue[currIdx]);
			System.out.print("<-");
			currIdx++;	
			if ((currIdx >= qSize)&& (lastIdx < firstIdx)) {currIdx=0;}
	} while(currIdx != lastIdx+1);
	System.out.println();
	System.out.println("**************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}  
  	
public static void main(String[] args) {
	/* Test Cases give below:	*/	
	try {
	QueueCircularArray queue=new QueueCircularArray();
	System.out.print("Add to Queue");
	queue.add(9);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(14);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(17);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(34);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(21);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(28);
	queue.printQueue();
	
	System.out.println("QUEUE ARRAY SIZE "+queue.getSize());
	
	System.out.print("\nRemove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	
	System.out.println("GET FIRST NODE "+queue.get());
	
	queue.remove();
	queue.printQueue();
	
	
	System.out.println("QUEUE ARRAY SIZE "+queue.getSize());
	System.out.println("\nGET FIRST NODE "+queue.get());
	
	System.out.print("Add to Queue");
	queue.add(99);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(44);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.add(77);
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}