In the previous post I discussed about queue implementation using array. It has certain drawbacks such as when an element is dequeued from the front, all the elements have to be shifted to the left. This can give poor performance when the number of elements stored in the array becomes large. To solve this issue queue can be implemented using circular array. This post discusses queue using circular implementation, a diagrammatic representation, algorithm used and code implementation.
Prerequisites :
Knowledge of Java, basic data structures, working of queue, circular array and understanding of time and space complexity.
Check Queue implementation using array to learn how queue can be implemented using array in Java.
Explanation :
In the queue implementation using array, a major drawback is when an element is dequeued from the front of the array, all the elements have to be shifted to the left by 1 position. This works well when the number of elements is small. But when the number of elements stored in the array becomes large it can give poor performance.
To solve the above problem, queue can be implemented using circular array. Imagine the circular array as an array in which the last position is connected back to the first position to form a circle. It also follows the FIFO principle.
Important terms used :
- SPECIAL_EMPTY_VALUE : This is a final variable with value -1. And it is used to initialize front and rear index to -1.
- front : This is the pointer to the front element of the queue. It is initialized with SPECIAL_EMPTY_VALUE.
- rear : This is the pointer to the rear/last element of the queue. It is initialized with SPECIAL_EMPTY_VALUE.
Operations that can be performed on a circular queue :
- int front() : Returns the front element of the queue.
- int rear() : Returns the rear element of the queue.
- boolean isEmpty() : This method returns true if the queue is empty by comparing the front with SPECIAL_EMPTY_VALUE. If front is equal to SPECIAL_EMPTY_VALUE, it means that the queue is empty and it returns true, else it returns false.
- boolean isFull() : This method returns true if the queue is full. The queue is full when the next index of rear is equal to the front index i.e. both rear and front are adjacent to each other. If the queue is not full this method returns false.
- boolean enQueue(int value) : This method first checks if the queue is full, if yes then it returns false and does not enqueue any element to the queue. If the queue is not full then it finds the next index of rear, enqueues an element at that index and returns true.
- boolean deQueue() : deQueue method first checks if the queue is empty. If it is empty then it returns false. If it is not empty, then it dequeues an element from the front and next index of front is calculated.
Algorithm :
- Initialize front and rear pointers with SPECIAL_EMPTY_VALUE of -1.
- To enqueue an element, check if the queue is full. The queue is full when the next index of rear is equal to the front index i.e (rear + 1) % queue.length == front. If the queue is full then no element is enqueued else new element is inserted at index (rear + 1) % queue.length.
- To dequeue an element, check if the queue is empty. The queue is empty when front has SPECIAL_EMPTY_VALUE. If the queue is empty then no element can be dequeued else the front element is dequeued and next index of front is calculated using (front + 1) % queue.length.
Diagrammatic representation :
Code implementation :
class CircularQueue {
int queue[];
private static final int SPECIAL_EMPTY_VALUE = -1;
private static int front;
private static int rear;
/**
* Initialize your data structure here. Set the size of the queue to be k.
*/
public CircularQueue(int k) {
queue = new int[k];
front = SPECIAL_EMPTY_VALUE;
rear = SPECIAL_EMPTY_VALUE;
}
/**
* Insert an element into the circular queue. Return true if the operation
* is successful.
*/
public boolean enQueue(int value) {
if (isFull()) {
System.out.println("Queue is full.Cannot enqueue new element = " + value);
return false;
} else {
// find next position of rear where new element will be placed
rear = (rear + 1) % queue.length;
queue[rear] = value;
// change the index of front, for the first element inserted
if (front == SPECIAL_EMPTY_VALUE)
front = rear;
System.out.println("Element enqueued = " + queue[rear]);
return true;
}
}
/**
* Delete an element from the circular queue. Return true if the operation
* is successful.
*/
public boolean deQueue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue element.");
return false;
} else {
// if this is the last element in the queue
if (front == rear) {
System.out.println("Element dequeued = " + queue[front]);
front = SPECIAL_EMPTY_VALUE;
rear = SPECIAL_EMPTY_VALUE;
} else {
System.out.println("Element dequeued = " + queue[front]);
front = (front + 1) % queue.length;
}
return true;
}
}
/** Get the front item from the queue. */
public int front() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot find front element.");
return -1;
} else {
System.out.println("Front element = " + queue[front]);
return queue[front];
}
}
/** Get the last item from the queue. */
public int rear() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot find rear element.");
return -1;
} else {
System.out.println("Rear element = " + queue[rear]);
return queue[rear];
}
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return front == SPECIAL_EMPTY_VALUE;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
// queue is full when next index of tail is equal to head index
int nextIndexOfTail = (rear + 1) % queue.length;
return nextIndexOfTail == front;
}
public static void main(String[] args) {
CircularQueue q = new CircularQueue(5);
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
q.enQueue(6);
q.deQueue();
q.deQueue();
q.front();
q.rear();
q.deQueue();
q.deQueue();
q.deQueue();
q.deQueue();
}
}
Code output :
Element enqueued = 1
Element enqueued = 2
Element enqueued = 3
Element enqueued = 4
Element enqueued = 5
Queue is full.Cannot enqueue new element = 6
Element dequeued = 1
Element dequeued = 2
Front element = 3
Rear element = 5
Element dequeued = 3
Element dequeued = 4
Element dequeued = 5
Queue is empty. Cannot dequeue element.
Time and space complexity :
Time complexity of all the operations enQueue(), deQueue(), isEmpty(), isFull(), front(), rear() is O(1) since we do not loop over the array elements to perform any of these operations. Hence the number of steps required to perform these operations is constant time complexity.
Space complexity of the algorithm is O(N) where N is the number of elements stored in the array.
Link to the above code on my github profile, Queue using circular array.
Thank you so much for reading. Your feedback is highly appreciated..!!
Data structures and algorithms in Java 