# Question & Answer: Priority Queue Suppose we define a priority queue using a circular doubly linked list as follows: struct node { /* Linked list node *…..

Priority Queue Suppose we define a priority queue using a circular doubly linked list as follows: struct node { /* Linked list node */ int info;/* info stored in this node */ struct node *next;/* Pointer to the next node in linked list *//*(or the front node of LL if this is the rear node) */ struct node *prev;/* Pointer to the next node in linked list *//*(or the rear node of LL if this is the front node) */ }: struct pq {/*Priority queue */ int size;/* Number of elements in queue */ struct node *front;/*pointer to the first node */ struct node *rear;/* Pointer to the last node */ }: Write an iterative (i.e., non-recursive) function to insert the given node, new, into a sorted priority queue. void insert (struct pq *queue, struct node *new){

void insert(struct pq *queue, struct node *new)
{
if(new->info <= queue->front->info) // If new is the smallest node
{
// first connecting new to previous an next nodes
new->next = queue->front;
new->prev = queue->rear;
// then connecting previous and nodes to new
queue->front->prev = new;
queue->rear->next = new;
// Changing front node to new
queue->front = new;
}
else if(new->info >= queue->rear) // If new is the largest node
{
// first connecting new to previous an next nodes
new->prev = queue->rear;
new->next = queue->front;
// then connecting previous and nodes to new
queue->rear->next = new;
queue->front->prev = new;
// Changing rear node to new
queue->rear = new;
}
else // if new is meant for somewhere in the middle
{
struct node *ptr = queue->front->next;
while(ptr != rear){ // Looking for new’s position by traversing from front to rear
if(new->info <= ptr->info){ // if new’s position found
// first connecting new to previous an next nodes
new->next = ptr;
new->prev = ptr->prev;
// then connecting previous and nodes to new
ptr->prev->next = new;
ptr->prev = new;
}
}
}
queue->size += 1; // increasing queue size by 1
}