Queue Implementation using Circular Array in Java

---

< Previous Next >

DS and Algorithms in Java

---

In this article, we will learn how to implement a Queue using an Array in Java.

This a simple implementation of Queue Abstract Data Type uses an Array. In the array, we add elements circularly and use two variables to keep track of the start element and end element. Generally, a front is used to indicate the start element and rear is used to indicate the end element in the queue.

The array storing the queue elements may become full.  An EnQueue operation will then throw a full queue exception. Similarly, if we try deleting an element from an empty queue it will throw empty queue exception.

Note: Initially, both front and rear points to -1 which indicates that the queue is empty.

Queue Implementation using Circular Array

Note that the size of the array is fixed to 16. If will try to add elements to a queue throw a full queue exception.

package com.javaguides.javads.queues;

/**
 * Queue Implementation using Circular Array
 * @author Ramesh Fadatare
 *
 */
public class FixedSizeArrayQueue{ 
 // Array used to implement the queue.
 private int[] queueRep;
 private int size, front, rear;
 
 // Length of the array used to implement the queue.
 private static final int CAPACITY = 16; //Default Queue size

 // Initializes the queue to use an array of default length.
 public FixedSizeArrayQueue (){
  queueRep = new int [CAPACITY];
  size  = 0; front = 0; rear  = 0;
 }
 
 // Initializes the queue to use an array of given length.
 public FixedSizeArrayQueue (int cap){
  queueRep = new int [ cap];
  size  = 0; front = 0; rear  = 0;
 }
 
 // Inserts an element at the rear of the queue. This method runs in O(1) time.
 public void enQueue (int data)throws NullPointerException, IllegalStateException{  
  if (size == CAPACITY)
   throw new IllegalStateException ("Queue is full: Overflow");
  else {
   size++;
   queueRep[rear] = data;
   rear = (rear+1) % CAPACITY;
  }
 }

 // Removes the front element from the queue. This method runs in O(1) time.
 public int deQueue () throws IllegalStateException{
  // Effects:   If queue is empty, throw IllegalStateException,
  // else remove and return oldest element of this
  if (size == 0)
   throw new IllegalStateException ("Queue is empty: Underflow");
  else {
   size--;
   int data = queueRep [ (front % CAPACITY) ];
   queueRep [front] = Integer.MIN_VALUE;
   front = (front+1) % CAPACITY;
   return data;
  }
 }

 // Checks whether the queue is empty. This method runs in O(1) time.
 public boolean isEmpty(){ 
  return (size == 0); 
 }
 
 // Checks whether the queue is full. This method runs in O(1) time.
 public boolean isFull(){ 
  return (size == CAPACITY); 
 }
 
 // Returns the number of elements in the queue. This method runs in O(1) time.
 public int size() {
  return size;
 }
 
 // Returns a string representation of the queue as a list of elements, with
 // the front element at the end: [ ... , prev, rear ]. This method runs in O(n)
 // time, where n is the size of the queue. 
 public String toString(){
  String result = "[";
  for (int i = 0; i < size; i++){
   result += Integer.toString(queueRep[ (front + i) % CAPACITY ]);
   if (i < size -1) {
    result += ", ";
   }
  }
  result += "]";
  return result;
 }

 public static void main(String[] args) {
     FixedSizeArrayQueue arrayQueue = new FixedSizeArrayQueue();
     arrayQueue.enQueue(10);
     arrayQueue.enQueue(20);
     arrayQueue.enQueue(30);
     arrayQueue.enQueue(40);
     arrayQueue.enQueue(50);
     arrayQueue.enQueue(60);
     arrayQueue.enQueue(70);
     arrayQueue.enQueue(80);
     arrayQueue.enQueue(90);
     arrayQueue.deQueue();
     System.out.println(arrayQueue.toString());
 }
}

Output:

[20, 30, 40, 50, 60, 70, 80, 90]

Let's add few more elements to queue so that queue will throw full queue exception.

public static void main(String[] args) {
     FixedSizeArrayQueue arrayQueue = new FixedSizeArrayQueue();
     arrayQueue.enQueue(10);
     arrayQueue.enQueue(20);
     arrayQueue.enQueue(30);
     arrayQueue.enQueue(40);
     arrayQueue.enQueue(50);
     arrayQueue.enQueue(60);
     arrayQueue.enQueue(70);
     arrayQueue.enQueue(80);
     arrayQueue.enQueue(100);
     arrayQueue.enQueue(101);
     arrayQueue.enQueue(102);
     arrayQueue.enQueue(103);
     arrayQueue.enQueue(104);
     arrayQueue.enQueue(105);
     arrayQueue.enQueue(106);
     arrayQueue.enQueue(107);
     arrayQueue.enQueue(108);
     System.out.println(arrayQueue.toString());
 }

Output:

Exception in thread "main" java.lang.IllegalStateException: Queue is full: Overflow
 at com.javaguides.javads.queues.FixedSizeArrayQueue.enQueue(FixedSizeArrayQueue.java:31)
 at com.javaguides.javads.queues.FixedSizeArrayQueue.main(FixedSizeArrayQueue.java:102)

Performance and Limitations

Performance

Let n be the number of elements in the queue:

• Space Complexity (for n enQueue operations) O(n)
• Time Complexity of enQueueQ O(1)
• Time Complexity of deQueueQ O(1)
• Time Complexity of isEmpty() O(1)
• Time Complexity of isFull () O(1)
• Time Complexity of getQueueSize () O(1)

Limitations

The maximum size of the queue must be defined as prior and cannot be changed. Trying to EnQueue a new element into a full queue causes an implementation-specific exception.

---

< Previous Next >

DS and Algorithms in Java

---