Queue No-count approach and Implementation

If you check our previous article Queue Example with count approach, the field nElements in MyQueue class imposes slight overhead on the insert() and remove() methods as these methods increments and decrements this variable.

When you deal with huge number of insertion and deletion operations, it might affect the performance. That’s why some Queues will be implemented without an element count variable in the program.

In the following example Queue, no-count approach, you can rely on front and rear fields to check whether the queue is full or empty or to check how many items or elements are there in the queue.

Example: Queue no-count approach

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;
	
	public int getFront()
	{
		return front;
	}
	
	public int getRear()
	{
		return rear;
	}
	
	public MyQueue(int size)
	{
		//set queue array size 1 cell larger then needed to avoid the following problem:
		//queue can appear full and empty at the same time
		maxQueueArraySize = size+1;
		//create array
		myQueueArray = new long[maxQueueArraySize];		
		front = 0;		
		rear = -1;	
	}
	
	//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;
		
	}
	
	//remove element from front of the Queue.
	public long remove()
	{
		long temp = myQueueArray[front++];
		if(front == maxQueueArraySize)
			front = 0;
				
		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 (rear+1==front ||
				(front+maxQueueArraySize-1==rear));
	}
	
	//return true is queue is full
	public boolean isFull()
	{
		return (rear+2==front ||
				(front+maxQueueArraySize-2==rear));
	}
	
	//return number of elements in the Queue
	public int size()
	{
		if(rear>=front)
			return rear-front+1;
		else
			return(maxQueueArraySize-front)+(rear+1);
	}
}
/**
 * 
 * @author sneppets.com
 *
 */
public class QueueWithoutCountExample {
	
	public static void main (String[] args)
	{
		//create queue using MyQueue that can hold 4 items
		MyQueue myQueue = new MyQueue(4);
		
		//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());
		
		//remove 2 elements. 
		//call isEmpty()to ensure that there are elements in the queue before calling remove()
		if (!myQueue.isEmpty())
			myQueue.remove();
		if (!myQueue.isEmpty())
			myQueue.remove();
		
		//insert 3 more items
		myQueue.insert(9);
		myQueue.insert(11);
		myQueue.insert(13);
		
		while (!myQueue.isEmpty())
		{
			long element = myQueue.remove();
			System.out.println(element);
		}
	}

}

Output

Peek Front: 3
Peek Rear: 7
7
9
11
13

Recommended Posts

• Circular Queue using Array (Wrap Around)
• Array based Queue implementation
• Reverse a string or word using Stack
• Delimiter matching using Stack

References

• Oracle API Documentation