Implement Queue Using Array in Java

by Online Tutorials Library July 22, 2022

Implement Queue Using Array in Java

The queue is a type of data structure that can be implemented using an array or a linked list. Here, we have given a brief knowledge of the process of implementing a queue using an array.

Queue

A queue is data structure that is based on first-in first-out (FIFO) in which the first item input is also the first item removed. Items are added to the end of the line and removed from the beginning.

When utilising an array to construct a queue, the fact that an array has a fixed size once declared poses an issue in the queue implementation. When elements are added to a queue and then deleted, a gap is created. To fill the gap, we can rearrange the remaining components to fill the space, but it is a time-consuming procedure. Another alternative is to use a circular queue, with the front and back pointing to the beginning of the array after the maximum size has been achieved.

Queue Implementation in Java

Queue Operations

For a Queue-based system, the following three operations are used.

insert: To add an item at the back / rear end of the queue.

remove: To delete an item from the front of the queue.

peek: Get a value from the front of the queue without having to remove it.

Java Program for Queue Implementation Using an Array

DemoQueue.java

  public class DemoQueue   {    /* Member variable declaration */    private int maxSize;    private int[] queueArray;    private int front;    private int rear;    private int currentSize;    /* Constructor */    public DemoQueue(int size)    {      this.maxSize = size;      this.queueArray = new int[size];      front = 0;      rear = -1;      currentSize = 0;    }    /* Queue:Insert Operation */    public void insert(int item)    {      /* Checks whether the queue is full or not */      if(isQueueFull())      {        System.out.println(“Queue is full!”);        return;      }      if(rear == maxSize – 1)  {        rear = -1;      }      /* increment rear then insert element to queue */      queueArray[++rear] = item;      currentSize++;      System.out.println(“Item added to queue: ” + item);    }    /* Queue:Delete Operation */      public int delete()    {      /* Checks whether the queue is empty or not */      if(isQueueEmpty())      {        throw new RuntimeException(“Queue is empty”);      }      /* retrieve queue element then increment */      int temp = queueArray[front++];      if(front == maxSize)      {        front = 0;      }      currentSize–;      return temp;    }    /* Queue:Peek Operation */        public int peek()    {      return queueArray[front];    }    /* Queue:isFull Operation */     public boolean isQueueFull()    {      return (maxSize == currentSize);    }        /* Queue:isEmpty Operation */     public boolean isQueueEmpty()  {      return (currentSize == 0);    }    /* Driver Code */    public static void main(String[] args)     {      DemoQueue queue = new DemoQueue(10);      queue.insert(2);      queue.insert(3);      System.out.println(“Item deleted from queue: ” + queue.delete());      System.out.println(“Item deleted from queue: ” + queue.delete());      queue.insert(5);          System.out.println(“Item deleted from queue: ” + queue.delete());        }  }  

Output:

Item added to queue: 2  Item added to queue: 3  Item deleted from queue: 2  Item deleted from queue: 3  Item added to queue: 5  Item deleted from queue: 5

As you can see from the code there are insertions and deletions as the front and back progress towards the higher index. Though not implemented as a circular queue, it will result in the queue becoming full and unable to accept new items, even if space has been made in the front due to the deletions.

CurrentSize is a field that is increased with each entry and decremented with each removal to keep track of the current size. If maxSize = currentSize, the queue is genuinely full; otherwise, even if maxSize is reached, there remains room at the front that may be utilised to start from the beginning by wrapping the back. Similarly, after maxSize is reached, front can be wrapped to start from the beginning.

Performance of Queue

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

Next TopicJava 13 Features

Implement Queue Using Array in Java

Implement Queue Using Array in Java

Queue

Queue Implementation in Java

Java Program for Queue Implementation Using an Array

Performance of Queue

How to Take Multiple String Input in Java Using Scanner

Java constructor returns a value, but what

You may also like