Implementation of a Circular Resizable Array in Java
A Circular Resizable Array is a data structure that effectively maintains a fixed-size array by enabling members to be added or withdrawn circularly. It is sometimes referred to as a circular buffer or ring buffer. This cyclical behavior is especially helpful in situations when a smooth array wrap is required and a continuous data flow is anticipated. In this tutorial, we will look at how to create a circular resizable array in Java.
Prerequisites:
Circular Resizable Array
The fundamental principle underlying a circular resizable array is keeping two pointers, one for the array’s head and another for its tail. When items are added or withdrawn, these pointers travel in a circle within the array’s boundaries. The array may dynamically expand itself to make room for extra items as it fills up.
Implementation:
Let’s implement a basic version of a circular resizable array in Java.
Java
// Java Program to Implement // Circular Resizable Array public class CircularArray { private int [] array; private int size; private int head; private int tail; // Constructor public CircularArray( int capacity) { array = new int [capacity]; size = 0 ; head = 0 ; tail = 0 ; } // Enqueue (Add Element) Method public void enqueue( int element) { if (size == array.length) { resizeArray(); } array[tail] = element; tail = (tail + 1 ) % array.length; size++; } // Dequeue (Remove Element) Method public int dequeue() { if (isEmpty()) { throw new IllegalStateException( "Circular array is empty" ); } int removedElement = array[head]; head = (head + 1 ) % array.length; size--; return removedElement; } // ResizeArray Method private void resizeArray() { int newCapacity = array.length * 2 ; int [] newArray = new int [newCapacity]; for ( int i = 0 ; i < size; i++) { newArray[i] = array[(head + i) % array.length]; } array = newArray; head = 0 ; tail = size; } // Check if CircularArray is empty public boolean isEmpty() { return size == 0 ; } // Main method for testing public static void main(String[] args) { CircularArray circularArray = new CircularArray( 5 ); circularArray.enqueue( 1 ); circularArray.enqueue( 2 ); circularArray.enqueue( 3 ); circularArray.enqueue( 4 ); circularArray.enqueue( 5 ); System.out.println( "Dequeuing: " + circularArray.dequeue()); System.out.println( "Dequeuing: " + circularArray.dequeue()); circularArray.enqueue( 6 ); circularArray.enqueue( 7 ); System.out.println( "Dequeuing: " + circularArray.dequeue()); } } |
Dequeuing: 1 Dequeuing: 2 Dequeuing: 3
Explaination of the above Program
1. Defining Class:
CircularArray is a Java class that is defined in the code.
public class CircularArray
2. Instance Variables:
private int[] array;
private int size;
private int head;
private int tail;
The circular array is managed by these private instance variables:
- array: The element-storing underlying array.
- size: The circular array’s current element count.
- head: Indicates where the circular array’s front is located.
- tail: A pointer pointing to the circular array’s back.
3. Constructor:
public CircularArray(int capacity) {
array = new int[capacity];
size = 0;
head = 0;
tail = 0;
}
The circular array is initialized with a specified capacity by the class’s constructor. At first, the head and tail are both set to 0, as is the size.
4. Enqueue Method:
public void enqueue(int element) {
if (size == array.length) {
resizeArray();
}
array[tail] = element;
tail = (tail + 1) % array.length;
size++;
}
- An element is added to the circular array using the enqueue function.
- The resizeArray function is called to double the array’s capacity if size = array.length, indicating that the array is full.
- The tail is updated in a cyclical fashion once the new element is introduced at that place.
5. Dequeue Method:
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Circular array is empty");
}
int removedElement = array[head];
head = (head + 1) % array.length;
size--;
return removedElement;
- The element from the front of the circular array is removed and returned using the dequeue function.
- An exception is raised in case the array is empty.
- The size decreases as the head pointer is rotated in a circular motion.
6. Resize Array Method:
private void resizeArray() {
int newCapacity = array.length * 2;
int[] newArray = new int[newCapacity];
for (int i = 0; i < size; i++) {
newArray[i] = array[(head + i) % array.length];
}
array = newArray;
head = 0;
tail = size;
}
- When the array is filled, the resizeArray function is invoked.
- It replicates the current items, generates a new array twice as large, and modifies the array references for the head, tail, and elements.
7. isEmpty Method:
public boolean isEmpty() {
return size == 0;
}
The circular array’s empty status is determined via the isEmpty method.
Main Method for Testing:
Java
public static void main(String[] args) { CircularArray circularArray = new CircularArray( 5 ); circularArray.enqueue( 1 ); circularArray.enqueue( 2 ); circularArray.enqueue( 3 ); circularArray.enqueue( 4 ); circularArray.enqueue( 5 ); System.out.println( "Dequeuing: " + circularArray.dequeue()); System.out.println( "Dequeuing: " + circularArray.dequeue()); circularArray.enqueue( 6 ); circularArray.enqueue( 7 ); System.out.println( "Dequeuing: " + circularArray.dequeue()); } |
- The primary method queues and dequeues items to show how to use the circular array.
- The components that are being dequeued are output to the console.