Use a singly linked list to implement a priority queue with two operations: enqu
ID: 3867238 • Letter: U
Question
Use a singly linked list to implement a priority queue with two operations: enqueue and dequeue. Each node contains an integer value, a priority, and a pointer to the next node. The priority is a value between 1- 10 (where 10 is the highest priority). When a value is added to the queue, it is added with a value and priority. When a value is removed from the priority queue, the first element with the highest priority is removed first (not simply the first element). Function must have us enter a priority value as well as a value for the node! Must be written in C.
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
int priority;
struct node *next;
};
struct node *dequeue(struct node *head){
struct node *ptr,*ptr1,*ptr2;
struct node *temp;
int priority = 0;
if (head != NULL){
ptr = head;
while (ptr->next != NULL){
if (ptr->priority > priority){
priority = ptr->priority;
ptr2 = ptr;
}
ptr = ptr->next;
}
ptr = head;
while (ptr->next != NULL && ptr->next != ptr2){
ptr = ptr->next;
}
ptr->next = ptr2->next;
return ptr2;
}
else {
printf("Queue is empty ");
return NULL;
}
}
void printList(struct node *head){
struct node *ptr;
ptr = head;
while (ptr != NULL){
printf("%d ", ptr->data);
ptr = ptr->next;
}
}
struct node *enqueue(struct node *head, int n, int pri){
struct node *temp, *ptr;
temp = (struct node *)malloc(sizeof(struct node));
temp->next = NULL;
temp->data = n;
temp->priority = pri;
if (head == NULL){
head = temp;
}
else{
ptr = head;
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = temp;
}
return head;
}
int main(){
struct node *head1, *head2;
struct node *temp;
head1 = NULL;
head2 = NULL;
head1 = enqueue(head1, 45,5);
head1 = enqueue(head1, 56, 1);
head1 = enqueue(head1, 23,4);
head1 = enqueue(head1, 46,3);
head1 = enqueue(head1, 57, 10);
head1 = enqueue(head1, 24,8);
printf("Queue1 is as follows: ");
printList(head1);
temp = dequeue(head1);
printf(" Removed data is %d ", temp->data);
printf(" After dequeue operation Queue1 is as follows: ");
printList(head1);
printf(" ");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.