Priority Queue For this assignment you are to implement a class named PriorityQu

Question

Priority Queue For this assignment you are to implement a class named PriorityQueue, with the same methods Queuc discussed in class. Thc only difference is that the enqucue method now takes two arguments: an element to enqueue (of generic/templated type T), and an integer representing the element's prioritv, Feel free to implement the class using either a linked list or an array for its underlying typc. Write a program (pq.h) that contains: 1. Contains the PriorityQueue class as specified in the above paragraph 2. As wcll as any othcr classcs nccd to implement thc PriorityQucuc class (such as ListNodc and List) Write a program (pg.cpp) that 1. Includes thc pq.h filc Create an interactive "command" driven prompt system that parses "commands" from the uscr that arc uscd to invokc thc appropriate functions: 2. Prompt thc uscr to specify what data type thcy want the priority qucuc to contain (like for the generic vector program in Assignment 2) * Enter a looping prompt that parses the following commands with the appropriate parameters o enqueue o dequeue Print the returned value to standard out o first

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 push(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 pop(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;

    push(&front, &rear, 2, 3);

    push(&front, &rear, 3, 4);

    push(&front, &rear, 4, 5);

    push(&front, &rear, 5, 6);

    push(&front, &rear, 6, 7);

    push(&front, &rear, 1, 2);

    cout << pop(&front, &rear) << endl;

    cout << peek(front);

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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