Design a priority queue using a template class and a double linked list in c++.

Question

Design a priority queue using a template class and a double linked list in c++.

utc aily additional In the queue abstraction presented in this chapter, new items are always added at the end of the queue and wait their turn in line. For some programming applications, it is useful to extend the simple queue abstraction into a priority queue, in which the order of the items is determined by a numeric priority value. When an item is enqueued in a priority queue, it is inserted in the list ahead of any lower priority items. If two items in a queue have the same priority, they are processed in the standard first-in/first-out order. Using the linked-list implementation of queues as a model, design and implement a pqueue.h interface that exports a class called PriorityQueue. which exports the same methods as the traditional Queue class with the exception of the enqueue method, which now takes an additional argument as follows: void enqueue (ValueType value, double priority) ; The parameter value is the same as for the traditional versions of enqueue; the priority argument is a numeric value representing the priority. As in conventional English usage, smaller integers correspond to higher priorities, so that priority 1 comes before priority 2, and so forth.

Explanation / Answer

#include <bits/stdc++.h>
using namespace std;

// Linked List Node
struct Node {
int info;
int priority;
struct Node *prev, *next;
};

// Function to insert a new Node
void enqueue(Node** fr, Node** rr, int n, int p)
{
Node* news = (Node*)malloc(sizeof(Node));
news->info = n;
news->priority = p;

// If linked list is empty
if (*fr == NULL) {
*fr = news;
*rr = news;
news->next = NULL;
}
else {
// If p is less than or equal front
// node's priority, then insert at
// the front.
if (p <= (*fr)->priority) {
news->next = *fr;
(*fr)->prev = news->next;
*fr = news;
}

// If p is more rear node's priority,
// then insert after the rear.
else if (p > (*rr)->priority) {
news->next = NULL;
(*rr)->next = news;
news->prev = (*rr)->next;
*rr = news;
}

// Handle other cases
else {

// Find position where we need to
// insert.
Node* start = (*fr)->next;
while (start->priority > p)
start = start->next;
(start->prev)->next = news;
news->next = start->prev;
news->prev = (start->prev)->next;
start->prev = news->next;
}
}
}

// Return the value at rear
int peek(Node *fr)
{
return fr->info;
}

bool isEmpty(Node *fr)
{
return (fr == NULL);
}

// Removes the element with the
// least priority value form the list
int dequeue(Node** fr, Node** rr)
{
Node* temp = *fr;
int res = temp->info;
(*fr) = (*fr)->next;
free(temp);
if (*fr == NULL)
*rr = NULL;
return res;
}

// Diver code
int main()
{
Node *front = NULL, *rear = NULL;
enqueue(&front, &rear, 2, 3);
enqueue(&front, &rear, 3, 4);
enqueue(&front, &rear, 4, 5);
enqueue(&front, &rear, 5, 6);
enqueue(&front, &rear, 6, 7);
enqueue(&front, &rear, 1, 2);

cout << dequeue(&front, &rear) << endl;
cout << peek(front)<<" ";

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.