Queue Data Structure

Queue Data Structures in Java

Queue not only asked in interview to beginners but also asked to experienced professionals for all technologies. Queue is very important data in real world software application.

Definition : Queue is an abstract data type that follow the principle of FIFO (First-in-First-out), means the data that is inserted first will be removed first. In Queue enqueue operation (insertion of data) happen from rear and dequeue operation (removable of data) happen from from front. So in queue, in between insertion or deletion operations are not possible. If you want to remove a data from queue then it must be at front or remove all the data before your desired data and bring it at front end and remove.

We are going to discuss few examples below:-

1. When we call to customer care of mobile service provider, and banking service provider where volume of incoming call is high, you will hear "You are are in queue, please stay online.".
2. Shared printer also maintain the queue of printing jobs.
3. We can see the example of queue at bank. Where people use to wait for their turn to perform the transaction.

Implementation of Queue

Here we are going to implement queue in java. We will handle all the possible case like Queue overflow and underflow.Here list of basic operations those we are going to perform.

1. add : This operation will insert the element in queue.
2. remove : This operation will return the front element and remove it from queue.
3. Size : It will return the number of elements in queue.
4. isEmpty : This will return true if there is no element in queue else false.

 Queue can be implemented using array, linked list or stack. Here we are going to implement queue using array. We will also implement queue using linked list and stack but in another article.

We will discuss the algorithm step by step.

 Initially front and rear both point to 0. We will discuss why we are pointing front and rear to 0 when we check the condition of empty.

Step I          

Step II :   

Step III :  

Step IV : 

Step V :  

Step VI :

Step VII :

Explanation :

Here in step I we are pointing front and rear to 0, just to show that we do not have any data to dequeue and data to be inserted at position zero.

Now we discuss two basic operation enqueue and dequeue and we also discuss what is the size of queue(number of elements in queue) and when will be the queue empty. 

1. isEmpty : 

    

    Check from any queue and try to remove element one by one and find the condition where queue does not contain any element in it.

See at Step III Queue:

 front points at 2 and reat points at 8

 remove an element and increase front by 1, so  now front points at 3.

 remove one more element and increase front by 1, now front points at 4.

 likewise when front points at 7 and rear points at 8, we remove one element from position 7 increase  front by one. Now front and rear both are pointing to 8 and queue is empty.

So when front == rear then queue is empty.

 Follow the same procedure and check your queue when it is getting empty.

  

isEmpty
  return front==rear

2. Size :

    We are going to find the number of elements in queue at a particular time and that would be size of queue. Here we are checking boundary condition for overflow queue by total capacity minus one, so our modulus operation will work too.

Size 
    (capacity - front + rear) modulus  (capacity)

3. Enqueue
 
    If size of queue is equal to (capacity - 1) then return queue overflow else insert an element in queue and increase rear by one.

4. Dequeue
 
    If queue is empty return queue underflow else return element from front and increase front by one.

Exception Java class

package com.company.dataStructure.exception;

/**
 * @author 
 *
 */
public class QueueException extends RuntimeException {

 private static final long serialVersionUID = -7622234016049976464L;

 public QueueException() {
  super();
 }

 /**
  * @param message
  */
 public QueueException(String message) {
  super(message);
 }

 /**
  * @param cause
  */
 public QueueException(Throwable cause) {
  super(cause);
 }

 /**
  * @param message
  * @param cause
  */
 public QueueException(String message, Throwable cause) {
  super(message, cause);
 }
}

Queue implementation

package com.company.dataStructure.imp;

import com.company.dataStructure.exception.QueueException;

/**
 * @author 
 *
 */
public class Queue {

 private Object queue[];
 private int front = 0;
 private int rear = 0;
 private int capacity;
 
 /**
  *This default constructor will initialize the capacity with size 10.  
  */
 public Queue() {
  this(10);
 }
 /**
  *This constructor will initialize the object array with size
  * capacity+1.
  *We are increasing the user given capacity by one to check 
  *the condition of queue overflow.   
  */
 public Queue(int capacity) {
  this.capacity = capacity + 1;
  this.queue = new Object[this.capacity];
 }
 /**
  * This method will accept an element and store into queue and throw 
  * QueueException if queue is full.
  */
 public void add(T e){
  
  /* This condition will check availability of space 
   to store another element in queue.We need to keep 
   one space empty in queue to check the overflow 
    condition because if front and rear point to 
    same location then it will be condition like empty.
     */
  
  if(this.size() == this.capacity - 1){
   throw new QueueException("Queue overflow.");
  }else{
   queue[this.rear] = e;
   
   /*We are increasing the rear by one and taking the
     modulus of that with capacity.By this way we are 
     initializing the rear to next empty position in 
     queue. Check the case moving from Step IV to Step
      V and observe the use of modulus.
    */
   
   this.rear = (this.rear + 1) % this.capacity;
  }
 }

 /**
  * This method will remove the front element from queue and
  throw QueueException if queue is empty.
  */
 public T remove(){
  if(this.isEmpty()){
   throw new QueueException("Queue underflow.");
  }else{
   @SuppressWarnings("unchecked")
   T tempElement = (T)this.queue[this.front];
   this.queue[this.front] = null;
   
   /*We are increasing the front by one and taking the 
    modulus of that with capacity. By this way 
    we are initializing the front to next position 
    in queue.
    */
   
   this.front = (this.front +1 ) % (this.capacity);
   return tempElement;
  }
 }
 /**
  * This method will return the number of elements in queue.
  * 
  */
 public int size(){
  return (
    (this.capacity - this.front + this.rear) 
     % 
    (this.capacity)
    );
 }

 /**
  * 
  * This method will return true if queue is empty else false. 
  */
 public boolean isEmpty(){
  return this.front == this.rear;
 }
 
 /* Overridden this method to print the queue*/
 @Override
 public String toString() {

  StringBuilder builder = new StringBuilder();
  for (int i = 0; i < queue.length; i++) {
   builder.append(queue[i]+" ");
  }
  return "front : "+this.front+" rear : "+this.rear
    +"\n"+builder.toString();
 }
}

Java Class with main method to test Queue

package com.company.test;

import com.company.dataStructure.imp.Queue;

public class MainQueue {

/**

* @param args

*/

public static void main(String[] args) {

Queue<Integer> queue = new Queue<Integer>();

System.out.println(queue.size()+" : "+queue.isEmpty());

for (int i = 1; i < 11; i++) {

System.out.print("Size Befor : "+queue.size()+" : "+i);

queue.add(i);

System.out.println(" : Size After : "+queue.size());

}

System.out.println(queue);

System.out.print("\n\n"+queue.size()+" : ");

System.out.println(queue.isEmpty()+"\n\n");

for (int i = 1; i < 5; i++) {

System.out.print("Size Befor : "+queue.size()+" : ");

System.out.println(queue.remove()+" : Size After : "+queue.size());

}

queue.add(100);

System.out.println(queue);

}

}