Priority Queue using Arrays/heap/Linked List
#include <stdio.h>
#include <stdlib.h>
#define MAX 50
void insert(int);
void delete(int);
void create();
void check(int);
void display();
int prique[MAX];
int front, rear;
void main()
{
int n, ch;
printf("\n1 - Insert an element into queue");
printf("\n2 - Delete an element from queue");
printf("\n3 - Display queue elements");
printf("\n4 - Exit");
create();
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nEnter value to be inserted : ");
scanf("%d",&n);
insert(n);
break;
case 2:
printf("\nEnter value to delete : ");
scanf("%d",&n);
delete(n);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nChoice is incorrect, Enter a correct choice");
}
}
}
/* Function to create an empty priority queue */
void create()
{
front = rear = -1;
}
/* Function to insert value into priority queue */
void insert(int data)
{
if (rear >= MAX - 1)
{
printf("\nQueue overflow no more elements can be inserted");
return;
}
if ((front == -1) && (rear == -1))
{
front++;
rear++;
prique[rear] = data;
return;
}
else
check(data);
rear++;
}
/* Function to check priority and place element */
void check(int data)
{
int i,j;
for (i = 0; i <= rear; i++)
{
if (data >= prique[i])
{
for (j = rear + 1; j > i; j--)
{
prique[j] = prique[j - 1];
}
prique[i] = data;
return;
}
}
prique[i] = data;
}
/* Function to delete an element from queue */
void delete(int data)
{
int i;
if ((front==-1) && (rear==-1))
{
printf("\nQueue is empty no elements to delete");
return;
}
for (i = 0; i <= rear; i++)
{
if (data == prique[i])
{
for (; i < rear; i++)
{
prique[i] = prique[i + 1];
}
prique[i] = -99;
rear--;
if (rear == -1)
front = -1;
return;
}
}
printf("\n%d not found in queue to delete", data);
}
/* Function to display queue elements */
void display()
{
if ((front == -1) && (rear == -1))
{
printf("\nQueue is empty");
return;
}
for (; front <= rear; front++)
{
printf(" %d ", prique[front]);
}
front = 0;
}
Priority Queue Using Heap
/*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
int heap[MAX_SIZE];
int size = 0;
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void insert(int value) {
if (size >= MAX_SIZE) {
printf("Heap overflow\n");
return;
}
heap[size] = value;
int current = size;
int parent = (current - 1) / 2;
while (current > 0 && heap[current] > heap[parent]) {
swap(&heap[current], &heap[parent]);
current = parent;
parent = (current - 1) / 2;
}
size++;
}
int delete() {
if (size <= 0) {
printf("Heap underflow\n");
return -1;
}
int value = heap[0];
size--;
heap[0] = heap[size];
int current = 0;
int left_child = current * 2 + 1;
int right_child = current * 2 + 2;
int max_child = (heap[left_child] > heap[right_child]) ? left_child : right_child;
while (max_child < size && heap[current] < heap[max_child]) {
swap(&heap[current], &heap[max_child]);
current = max_child;
left_child = current * 2 + 1;
right_child = current * 2 + 2;
max_child = (heap[left_child] > heap[right_child]) ? left_child : right_child;
}
return value;
}
void display()
{
int i;
printf("The Priority Queue is..........\n");
for(i=0;i<size;i++)
printf("%d--",heap[i]);
}
void main()
{
int n, ch;
printf("\n1 - Insert an element into queue");
printf("\n2 - Delete an element from queue");
printf("\n3 - Display queue elements");
printf("\n4 - Exit");
while (1)
{
printf("\nEnter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("\nEnter value to be inserted : ");
scanf("%d",&n);
insert(n);
break;
case 2:
n=delete();
if(n!=-1)
printf("The highest priority elemnt is %d",n);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nChoice is incorrect, Enter a correct choice");
}
}
}
Priority Queue using Linked List
/*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
int priority;
struct node* next;
};
struct node* head = NULL;
void insert(int data, int priority) {
struct node* temp = (struct node*)malloc(sizeof(struct node));
temp->data = data;
temp->priority = priority;
if (head == NULL || priority < head->priority) {
temp->next = head;
head = temp;
}
else {
struct node* current = head;
while (current->next != NULL && current->next->priority <= priority) {
current = current->next;
}
temp->next = current->next;
current->next = temp;
}
}
void delete() {
if (head == NULL) {
printf("Queue is empty\n");
}
else {
struct node* temp = head;
printf("Deleted item: %d\n", temp->data);
head = head->next;
free(temp);
}
}
void display() {
if (head == NULL) {
printf("Queue is empty\n");
}
else {
struct node* current = head;
printf("Queue elements:\n");
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
}
int main() {
insert(4, 2);
insert(2, 3);
insert(5, 4);
insert(3, 1);
insert(1, 5);
display();
delete();
display();
return 0;
}
Comments
Post a Comment