In: Computer Science
Explain how do you do indexing in a circular queue? (java programing)
Circular queue avoids the wastage of space in a regular queue implementation using arrays.
Limitation of the regular Queue
As you can see in the above image, after a bit of enqueuing and dequeuing, the size of the queue has been reduced.
The indexes 0 and 1 can only be used after the queue is reset when all the elements have been dequeued.
How Circular Queue Works
Circular Queue works by the process of circular increment i.e. when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue.
Here, the circular increment is performed by modulo division with the queue size. That is,
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Circular queue representation
Circular Queue Operations
The circular queue work as follows:
1. Enqueue Operation
2. Dequeue Operation
However, the check for full queue has a new additional case:
REAR == SIZE - 1
FRONT = REAR + 1
The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.
Enque and Deque Operations
// Circular Queue implementation in Java
public class CQueue {
int SIZE = 5; // Size of Circular Queue
int front, rear;
int items[] = new int[SIZE];
CQueue() {
front = -1;
rear = -1;
}
// Check if the queue is full
boolean isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// Check if the queue is empty
boolean isEmpty() {
if (front == -1)
return true;
else
return false;
}
// Adding an element
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front = (front + 1) % SIZE;
}
return (element);
}
}
void display() {
/* Function to display status of Circular Queue */
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
} else {
System.out.println("Front -> " + front);
System.out.println("Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE)
System.out.print(items[i] + " ");
System.out.println(items[i]);
System.out.println("Rear -> " + rear);
}
}
public static void main(String[] args) {
CQueue q = new CQueue();
// Fails because front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
q.enQueue(6);
q.display();
int elem = q.deQueue();
if (elem != -1) {
System.out.println("Deleted Element is " + elem);
}
q.display();
q.enQueue(7);
q.display();
// Fails to enqueue because front == rear + 1
q.enQueue(8);
}
}
Circular Queue Complexity Analysis
The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).