Queue introduction and implementation in Java

Queue is more abstract entity like stack than array and many other data structures. The underlying mechanism used to implement queues is not visible to the user.

In queue first item inserted would be the first one to be removed (First-In-First-Out, FIFO). While in stack as we have seen the last item inserted would be the first one to be removed (LIFO principle).

Queue Operations

The two basic operations of a queue are

Inserting an item at the rear of the queue. Insert operation is also called as put or add or enque.
Removing an item from front of the queue. Remove operation is also called as delete or get or deque.

Rear of the queue is also called as back or tail or end. The front of the queue is also called as Head.

Application of Queue

Queues are used to model real-world situations like people waiting in a line at a bank ATM to get money, printer queue where many print jobs are waiting in a queue for printers to be available etc.,

Queue implementation in Java

The following program implements a queue in java using a class called MyQueue.

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(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 (wraps around)
		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

Queue introduction and implementation in Java

Queue Operations

Application of Queue

Queue implementation in Java

Recommended Posts

References