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.

Refer Queue Implementation in Java Using Linked List to see how to implement Queue using linked list in Java.

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.

Operations in a Queue

Mainly following three operations are implemented for a Queue-

insert- To insert an item at the rear of the queue.
remove- To remove an item from the front of the queue.
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

You may also like-

Tech Tutorials

Friday, May 20, 2022