DSA using Java - Queue

Overview

Queue is kind of data structure similar to stack with primary difference that the first item inserted is the first item to be removed (FIFO - First In First Out) where stack is based on LIFO, Last In First Out principal.

Queue Representation

Basic Operations

insert / enqueue − add an item to the rear of the queue.

remove / dequeue − remove an item from the front of the queue.

We re going to implement Queue using array in this article. There is few more operations supported by queue which are following.

Peek − get the element at front of the queue.

isFull − check if queue is full.

isEmpty − check if queue is empty.

Insert / Enqueue Operation

Whenever an element is inserted into queue, queue increments the rear index for later use and stores that element at the rear end of the storage. If rear end reaches to the last index and it is wrapped to the bottom location. Such an arrangement is called wrap around and such queue is circular queue. This method is also termed as enqueue operation.

pubpc void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      
      intArray[++rear] = data;
      itemCount++;
   }
}

Remove / Dequeue Operation

Whenever an element is to be removed from queue, queue get the element using front index and increments the front index. As a wrap around arrangement, if front index is more than array s max index, it is set to 0.

 	 	
pubpc int remove(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;  
}

Queue Implementation

Queue.java

package com.tutorialspoint.datastructure;

pubpc class Queue {
    
   private final int MAX;
   private int[] intArray;
   private int front;
   private int rear;
   private int itemCount;

   pubpc Queue(int size){
      MAX = size;
      intArray = new int[MAX];
      front = 0;
      rear = -1;
      itemCount = 0;
   }

   pubpc void insert(int data){
      if(!isFull()){
         if(rear == MAX-1){
            rear = -1;            
         }       

         intArray[++rear] = data;
         itemCount++;
      }
   }

   pubpc int remove(){
      int data = intArray[front++];
      if(front == MAX){
         front = 0;
      }
      itemCount--;
      return data;  
   }

   pubpc int peek(){
      return intArray[front];
   }

   pubpc boolean isEmpty(){
      return itemCount == 0;
   }

   pubpc boolean isFull(){
      return itemCount == MAX;
   }

   pubpc int size(){
      return itemCount;
   }    
}

Demo Program

QueueDemo.java

package com.tutorialspoint.datastructure;

pubpc class QueueDemo {
   pubpc static void main(String[] args){
      Queue queue = new Queue(6);
      
      //insert 5 items
      queue.insert(3);
      queue.insert(5);
      queue.insert(9);
      queue.insert(1);
      queue.insert(12);

      // front : 0
      // rear  : 4
      // ------------------
      // index : 0 1 2 3 4 
      // ------------------
      // queue : 3 5 9 1 12

      queue.insert(15);

      // front : 0
      // rear  : 5
      // ---------------------
      // index : 0 1 2 3 4  5 
      // ---------------------
      // queue : 3 5 9 1 12 15

      if(queue.isFull()){
         System.out.println("Queue is full!");   
      }


      //remove one item
      int num = queue.remove();
      System.out.println("Element removed: "+num);
      // front : 1
      // rear  : 5
      // -------------------
      // index : 1 2 3 4  5
      // -------------------
      // queue : 5 9 1 12 15

      //insert more items
      queue.insert(16);

      // front : 1
      // rear  : -1
      // ----------------------
      // index : 0  1 2 3 4  5
      // ----------------------
      // queue : 16 5 9 1 12 15

      //As queue is full, elements will not be inserted.
      queue.insert(17);
      queue.insert(18);
 
      // ----------------------
      // index : 0  1 2 3 4  5
      // ----------------------
      // queue : 16 5 9 1 12 15
      System.out.println("Element at front: "+queue.peek());

      System.out.println("----------------------");
      System.out.println("index : 5 4 3 2  1  0");
      System.out.println("----------------------");
      System.out.print("Queue:  ");
      while(!queue.isEmpty()){
         int n = queue.remove();            
         System.out.print(n +" ");
      }
   }
}

If we compile and run the above program then it would produce following result −

Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2  1  0
----------------------
Queue:  5 9 1 12 15 16