Here are the detailed explanation of Circular and Priority Queue:
Circular Queue:
Circular Queue is a linear data structure that follows the First-In-First-Out (FIFO) order like the Linear Queue.
• Additionally, the last position is connected back to the first position to form the circle. This solves the problem of the Linear Queue to use the memory space effectively.
Operations on Circular Queue:
- Front: Get the front item from the queue.
- Rear: Get the last item from the queue.
- En-Queue(): This function is used to insert an element into the circular queue. In a circular queue, the new element is always inserted at the rear position.
- De-Queue():This function is used to delete an element from the circular queue. In a circular queue, the element is always deleted from the front position
Circular Queue Complexity Analysis
The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).
Implementation of Circular Queue:
Here’s a simple implementation of a circular queue in Java:
public class CircularQueue {
private int[] array;
private int front; // Index of the front element
private int rear; // Index of the rear element
private int size; // Current number of elements in the queue
private int capacity; // Maximum capacity of the queue
// Constructor to initialize the circular queue with a given capacity
public CircularQueue(int capacity) {
this.capacity = capacity;
array = new int[capacity];
front = rear = -1;
size = 0;
}
// Method to check if the queue is empty
public boolean isEmpty() {
return size == 0;
}
// Method to check if the queue is full
public boolean isFull() {
return size == capacity;
}
// Method to enqueue an element into the circular queue
public void enqueue(int element) {
if (isFull()) {
System.out.println("Queue is full. Cannot enqueue.");
return;
}
if (isEmpty()) {
front = rear = 0;
} else {
rear = (rear + 1) % capacity; // Circular increment
}
array[rear] = element;
size++;
}
// Method to dequeue an element from the circular queue
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue is empty. Cannot dequeue.");
return -1;
}
int element = array[front];
if (front == rear) {
front = rear = -1;
} else {
front = (front + 1) % capacity; // Circular increment
}
size--;
return element;
}
// Method to get the front element of the circular queue without removing it
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty. No element to peek.");
return -1;
}
return array[front];
}
public static void main(String[] args) {
CircularQueue queue = new CircularQueue(5);
// Enqueue elements into the circular queue
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
// Dequeue and print elements from the circular queue
while (!queue.isEmpty()) {
System.out.println("Dequeued: " + queue.dequeue());
}
}
}Circular Queue Complexity Analysis
Creating a heap takes O(n) time while inserting into a heap (or priority queue) takes O(log(n)) time.
Priority Queue:
A priority queue is defined as a special type of queue in which each element is associated with a priority value.
- It is an abstract data type and a special kind of queue.
• It is somehow similar to a normal queue the only difference is in the priority queue all the elements of the queue are arranged according to their priority.
Operations on Priority Queue:
1.) Insertion:
When a new element is inserted in a priority queue, it moves to the empty slot from top to bottom and left to right. If the element is not in the correct order, the elements are swapped.
2.) Deletion
As you know that in a max heap, the maximum element is the root node. And it will remove the element which has maximum priority first. Thus, you remove the root node from the queue. This removal creates an empty slot, which will be further filled with new insertion.
3.) Peek
This operation helps to return the maximum element from Max Heap or the minimum element from Min Heap without deleting the node from the priority queue.
Implementation of Priority Queue:
Here’s a simple implementation of a priority queue in Java using a binary heap:
import java.util.Arrays;
public class PriorityQueue {
private int capacity;
private int size;
private int[] heap;
public PriorityQueue(int capacity) {
this.capacity = capacity;
this.size = 0;
this.heap = new int[capacity];
}
public void insert(int element) {
if (size == capacity) {
System.out.println("Priority queue is full. Cannot insert.");
return;
}
heap[size] = element;
heapifyUp(size);
size++;
}
public int remove() {
if (isEmpty()) {
System.out.println("Priority queue is empty. Cannot remove.");
return -1;
}
int removedElement = heap[0];
heap[0] = heap[size - 1];
size--;
heapifyDown(0);
return removedElement;
}
public int peek() {
if (isEmpty()) {
System.out.println("Priority queue is empty. No element to peek.");
return -1;
}
return heap[0];
}
public boolean isEmpty() {
return size == 0;
}
private void heapifyUp(int index) {
int parentIndex = (index - 1) / 2;
while (index > 0 && heap[index] > heap[parentIndex]) {
swap(index, parentIndex);
index = parentIndex;
parentIndex = (index - 1) / 2;
}
}
private void heapifyDown(int index) {
while (true) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int maxIndex = index;
if (leftChildIndex < size && heap[leftChildIndex] > heap[maxIndex]) {
maxIndex = leftChildIndex;
}
if (rightChildIndex < size && heap[rightChildIndex] > heap[maxIndex]) {
maxIndex = rightChildIndex;
}
if (maxIndex == index) {
break;
}
swap(index, maxIndex);
index = maxIndex;
}
}
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
public static void main(String[] args) {
PriorityQueue pq = new PriorityQueue(5);
pq.insert(5);
pq.insert(3);
pq.insert(8);
pq.insert(1);
System.out.println("Peek: " + pq.peek());
System.out.println("Remove: " + pq.remove());
System.out.println("Remove: " + pq.remove());
System.out.println("Remove: " + pq.remove());
System.out.println("Remove: " + pq.remove());
}
}Difference between Circular Queue and Priority Queue:
| Feature | Circular Queue | Priority Queue |
|---|---|---|
| Basic Structure | FIFO (First-In-First-Out) data structure | Heap-based data structure |
| Operation | Enqueue (add element), Dequeue (remove element) | Insert (add element), Remove (remove highest priority element) |
| Order | Elements are dequeued in the order they were enqueued | Elements are dequeued based on priority (highest priority first) |
| Use Cases | Used when data needs to be processed in the order it was received | Used when processing elements based on priority is required |
| Implementation | Typically implemented using arrays or linked lists | Implemented using binary heaps (e.g., max-heap for maximum priority) |
| Performance | Enqueue and dequeue operations typically have O(1) time complexity | Insertion and removal operations have O(log n) time complexity, where n is the number of elements |
| Example | Simulating printing jobs in a printer queue | Task scheduling in an operating system |
