Monday, February 18, 2019

Queue Implementation in Java Using Array

In this post we’ll see an implementation of Queue in Java using array. Queue can also be implemented using Linked list.

Queue data structure

A queue is a First In First Out (FIFO) data structure where the first item inserted is the first to be removed. In a queue items are inserted at the rear and removed from the front of the queue.

When you implement queue using array, fact that an array once defined has a fixed size causes problem in the queue implementation. When items are inserted in a queue and later removed that creates a gap, to fill that gap you can shift the remaining elements to fill that space but that is an expensive operation. Another option is to implement a circular queue where front and rear start pointing to the beginning of the array once maximum size is reached.

Following image shows how circular queue works.

Queue implementation in Java

Operations in a Queue

Mainly following three operations are implemented for a Queue-

  1. insert- To insert an item at the rear of the queue.
  2. remove- To remove an item from the front of the queue.
  3. peek- Read value from the front of the queue without removing it.

Java program for Queue

public class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;
    public Queue(int size){
        this.maxSize = size;
        this.queueArray = new int[size];
        front = 0;
        rear = -1;
        currentSize = 0;
    }
    public void insert(int item){
        //check if queue is already full
        if(isQueueFull()){
            System.out.println("Queue is full!");
            return;
        }
        // for wrapping the queue in case 
        //  max size has reached
        if(rear == maxSize - 1){
            rear = -1;
        }
        // increment rear then insert item
        queueArray[++rear] = item;
        currentSize++;
        System.out.println("Added to queue" + item);
    }
    
    public int remove(){
        //check if queue is empty
        if(isQueueEmpty()){
            throw new RuntimeException("Queue is empty");
        }
        //System.out.println("front= " + front + " maxSize= "+maxSize);
        // retrieve item then increment
        int temp = queueArray[front++];
        if(front == maxSize){
            front = 0;
        }
        currentSize--;
        return temp;
    }
    public int peek(){
        return queueArray[front];
    }
    public boolean isQueueFull(){
        return (maxSize == currentSize);
    }
    
    public boolean isQueueEmpty(){
        return (currentSize == 0);
    }
    public static void main(String[] args) {
        Queue queue = new Queue(10);
        queue.insert(2);
        queue.insert(3);
        System.out.println("Item removed- " + queue.remove());
        System.out.println("Item removed- " + queue.remove());
        queue.insert(5);    
        System.out.println("Item removed- " + queue.remove());
        
    }
}

Output

Added to queue2
Added to queue3
Item removed- 2
Item removed- 3
Added to queue5
Item removed- 5

As you can see from the image as well as in the code both front and rear move towards the higher index and there are insertions and removals. That will result in Queue becoming full and not able to take new items even if there is space created in the front because of the removals, if not implemented as circular queue.

To keep track of the current size there is a field currentSize which is incremented with each insertion and decremented with each removal. If maxSize == currentSize that means queue is actually full otherwise even if maxSize is reached there is space created at the front which can be used by wrapping the rear to start from the beginning. Same way front can also be wrapped to start from the beginning once it reaches maxSize.

Performance of queue

In queue items can be inserted and removed in O(1) time.

That's all for this topic Queue Implementation in Java Using Array. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page


Related Topics

  1. Linked List Implementation Java Program
  2. Stack Implementation in Java Using Array
  3. Insertion Sort Program in Java
  4. Producer-Consumer Java Program Using ArrayBlockingQueue
  5. Converting Numbers to Words - Java Program

You may also like-

  1. How to Add Double Quotes to a String - Java Program
  2. How to Remove Duplicate Elements From an Array - Java Program
  3. How to Format Date in Java Using SimpleDateFormat
  4. How to Write Excel File in Java Using Apache POI
  5. Difference Between ArrayList And LinkedList in Java
  6. Difference Between CountDownLatch And CyclicBarrier in Java
  7. Java Exception Handling And Method Overriding
  8. Tips For Improving MapReduce Performance