What is Priority Queue?
A priority queue is a data structure that allows efficient retrieval and insertion of items based on priority. They are widely used in computer science algorithms and applications to organize and store data and provide quick access to the most important elements. A priority queue can be implemented using a variety of data structures, including Arrays, linked lists, heaps, etc. Each of these implementations has strengths and weaknesses depending on the use case.
Characteristics of Priority Queue
· Every element in a priority queue has some priority associated with it.
· An element with a higher priority will be deleted before deleting the lesser priority.
· If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle.
Types
· Ascending Order - In ascending priority queues, the lower the priority number, the higher the priority. For example, get the numbers 1 through 5 in ascending order: 1, 2, 3, 4, 5. Therefore, the minimum number i.H. 1 is assigned the highest priority in the priority queue.
· Descending Order - In descending priority queues, the higher the priority number, the higher the priority. For example, get the numbers 1 through 5 in descending order: 5, 4, 3, 2, 1. Hence the maximum number, i. H. 5, is assigned as the highest priority in the priority queue.
Implementation of Priority Queue in C
// Priority Queue implementation in C
#include <stdio.h>
int size = 0;
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}
// Function to heapify the tree
void heapify(int array[], int size, int i) {
if (size == 1) {
printf("Single element in the heap");
} else {
// Find the largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && array[l] > array[largest])
largest = l;
if (r < size && array[r] > array[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&array[i], &array[largest]);
heapify(array, size, largest);
}
}
}
// Function to insert an element into the tree
void insert(int array[], int newNum) {
if (size == 0) {
array[0] = newNum;
size += 1;
} else {
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
}
}
}
// Function to delete an element from the tree
void deleteRoot(int array[], int num) {
int i;
for (i = 0; i < size; i++) {
if (num == array[i])
break;
}
swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
}
}
// Print the array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
}
// Driver code
int main() {
int array[10];
insert(array, 3);
insert(array, 4);
insert(array, 9);
insert(array, 5);
insert(array, 2);
printf("Max-Heap array: ");
printArray(array, size);
deleteRoot(array, 4);
printf("After deleting an element: ");
printArray(array, size);
}
Priority Queue Implementation Using Java tutorial.
What is Deque?
A Deque is a data structure used to store and manipulate data linearly. This is a double-sided queue. In other words, it can be used to add and remove items from both ends of the queue. This makes it an ideal choice for implementing queues, stacks, and other data structures that require quick element insertion or removal. Deque makes it easy to access the first or last item in a queue without iterating over the entire list. In addition, Deque also provides efficient search algorithms for finding specific items in lists.
Types
· Input Restricted - In the input restricted queue, insertion operation can be performed at only one end, while deletion can be performed from both ends.
· Output Restricted - In the output restricted queue, deletion operation can be performed at only one end, while insertion can be performed from both ends.
Implementation of Deque in C
// Deque implementation in C
#include <stdio.h>
#define MAX 10
void addFront(int *, int, int *, int *);
void addRear(int *, int, int *, int *);
int delFront(int *, int *, int *);
int delRear(int *, int *, int *);
void display(int *);
int count(int *);
int main() {
int arr[MAX];
int front, rear, i, n;
front = rear = -1;
for (i = 0; i < MAX; i++)
arr[i] = 0;
addRear(arr, 5, &front, &rear);
addFront(arr, 12, &front, &rear);
addRear(arr, 11, &front, &rear);
addFront(arr, 5, &front, &rear);
addRear(arr, 6, &front, &rear);
addFront(arr, 8, &front, &rear);
printf("\nElements in a deque: ");
display(arr);
i = delFront(arr, &front, &rear);
printf("\nremoved item: %d", i);
printf("\nElements in a deque after deletion: ");
display(arr);
addRear(arr, 16, &front, &rear);
addRear(arr, 7, &front, &rear);
printf("\nElements in a deque after addition: ");
display(arr);
i = delRear(arr, &front, &rear);
printf("\nremoved item: %d", i);
printf("\nElements in a deque after deletion: ");
display(arr);
n = count(arr);
printf("\nTotal number of elements in deque: %d", n);
}
void addFront(int *arr, int item, int *pfront, int *prear) {
int i, k, c;
if (*pfront == 0 && *prear == MAX - 1) {
printf("\nDeque is full.\n");
return;
}
if (*pfront == -1) {
*pfront = *prear = 0;
arr[*pfront] = item;
return;
}
if (*prear != MAX - 1) {
c = count(arr);
k = *prear + 1;
for (i = 1; i <= c; i++) {
arr[k] = arr[k - 1];
k--;
}
arr[k] = item;
*pfront = k;
(*prear)++;
} else {
(*pfront)--;
arr[*pfront] = item;
}
}
void addRear(int *arr, int item, int *pfront, int *prear) {
int i, k;
if (*pfront == 0 && *prear == MAX - 1) {
printf("\nDeque is full.\n");
return;
}
if (*pfront == -1) {
*prear = *pfront = 0;
arr[*prear] = item;
return;
}
if (*prear == MAX - 1) {
k = *pfront - 1;
for (i = *pfront - 1; i < *prear; i++) {
k = i;
if (k == MAX - 1)
arr[k] = 0;
else
arr[k] = arr[i + 1];
}
(*prear)--;
(*pfront)--;
}
(*prear)++;
arr[*prear] = item;
}
int delFront(int *arr, int *pfront, int *prear) {
int item;
if (*pfront == -1) {
printf("\nDeque is empty.\n");
return 0;
}
item = arr[*pfront];
arr[*pfront] = 0;
if (*pfront == *prear)
*pfront = *prear = -1;
else
(*pfront)++;
return item;
}
int delRear(int *arr, int *pfront, int *prear) {
int item;
if (*pfront == -1) {
printf("\nDeque is empty.\n");
return 0;
}
item = arr[*prear];
arr[*prear] = 0;
(*prear)--;
if (*prear == -1)
*pfront = -1;
return item;
}
void display(int *arr) {
int i;
printf("\n front: ");
for (i = 0; i < MAX; i++)
printf(" %d", arr[i]);
printf(" :rear");
}
int count(int *arr) {
int c = 0, i;
for (i = 0; i < MAX; i++) {
if (arr[i] != 0)
c++;
}
return c;
}
Also, Read - Queue Data Structure and Implementation - 1