Question

****NEED CODED IN C++****

You are to generate a list of customers to serve based on the customer’s priority, i.e. create a priority queue/list for a local company. The company has been receiving request and the request are recorded in a file, in the order the request was made. The company processes each user based on their priority, the highest priority which is the largest number. Priorities of equal value are first come first served as listed in the input file. You input is a collection of customer IDs and priority, one pre line. You are to read in the data and insert new data into a sorted link list. The link list is sorted by priority.

A customer may need an update on his order. He may submit a request a second time in order to change his priority level. If so, you will search the link list, change the priority and adjust the new order in the sorted link list.

Input file: Priority Queue.txt

Output: List of ID’s with priorities in priority order

   Example input:

1345 4

8243 1

   Example output:

Customer Processing Order

Customer ID Priority

4124 5
1345 4

          …. ....

Restrictions: Use an ordered link list for the data structure and a nice formatted print out.

Input file (Priority Queue.txt):

1432 2
8234 3
2124 5
8123 2
1314 2
1432 4
7141 3
7123 4
5523 1
6543 2
1731 5
3813 4
7213 5
3318 5
7213 3
7131 2
8882 3
9974 1
7221 3
7342 4
5523 3
3113 5
7002 4
9769 1
3145 5
7145 3
8834 2
9123 4
7878 1
7588 4
2025 1
6069 3
2025 3

Answer 1

Algorithm :
PUSH(HEAD, DATA, PRIORITY)
Step 1: Create new node with DATA and PRIORITY
Step 2: Check if HEAD has lower priority. If true follow Steps 3-4 and end. Else goto Step 5.
Step 3: NEW -> NEXT = HEAD
Step 4: HEAD = NEW
Step 5: Set TEMP to head of the list
Step 6: While TEMP -> NEXT != NULL and TEMP -> NEXT -> PRIORITY > PRIORITY
Step 7: TEMP = TEMP -> NEXT
[END OF LOOP]
Step 8: NEW -> NEXT = TEMP -> NEXT
Step 9: TEMP -> NEXT = NEW
Step 10: End

POP(HEAD)
Step 2: Set the head of the list to the next node in the list. HEAD = HEAD -> NEXT.
Step 3: Free the node at the head of the list
Step 4: End

PEEK(HEAD):
Step 1: Return HEAD -> DATA
Step 2: End

// C++ code to implement Priority Queue
// using Linked List
#include <bits/stdc++.h>
using namespace std;

// Node
typedef struct node
{
   int data;

   // Lower values indicate
   // higher priority
   int priority;

   struct node* next;

} Node;

// Function to create a new node
Node* newNode(int d, int p)
{
   Node* temp = (Node*)malloc(sizeof(Node));
   temp->data = d;
   temp->priority = p;
   temp->next = NULL;

   return temp;
}

// Return the value at head
int peek(Node** head)
{
   return (*head)->data;
}

// Removes the element with the
// highest priority form the list
void pop(Node** head)
{
   Node* temp = *head;
   (*head) = (*head)->next;
   free(temp);
}

// Function to push according to priority
void push(Node** head, int d, int p)
{
   Node* start = (*head);

   // Create new Node
   Node* temp = newNode(d, p);

   // Special Case: The head of list has
   // lesser priority than new node. So
   // insert newnode before head node
   // and change head node.
   if ((*head)->priority > p)
   {
      
       // Insert New Node before head
       temp->next = *head;
       (*head) = temp;
   }
   else
   {
      
       // Traverse the list and find a
       // position to insert new node
       while (start->next != NULL &&
           start->next->priority < p)
       {
           start = start->next;
       }

       // Either at the ends of the list
       // or at required position
       temp->next = start->next;
       start->next = temp;
   }
}

// Function to check is list is empty
int isEmpty(Node** head)
{
   return (*head) == NULL;
}

// Driver code
int main()
{
  
   // Create a Priority Queue
   Node* pq = newNode(1432 ,2);
push(&pq, 8234 ,3);
push(&pq, 2124 ,5);
push(&pq, 8123 ,2);
push(&pq, 1314 ,2);
push(&pq, 1432 ,4);
push(&pq, 7141 ,3);
push(&pq, 7123 ,4);
push(&pq, 5523 ,1);
push(&pq, 6543 ,2);
push(&pq, 1731 ,5);
push(&pq, 3813 ,4);
push(&pq, 7213 ,5);
push(&pq, 3318 ,5);
push(&pq, 7213 ,3);
push(&pq, 7131 ,2);
push(&pq, 8882 ,3);
push(&pq, 9974 ,1);
push(&pq, 7221 ,3);
push(&pq, 7342 ,4);
push(&pq, 5523 ,3);
push(&pq, 3113 ,5);
push(&pq, 7002 ,4);
push(&pq, 9769 ,1);
push(&pq, 3145 ,5);
push(&pq, 7145 ,3);
push(&pq, 8834 ,2);
push(&pq, 9123 ,4);
push(&pq, 7878 ,1);
push(&pq, 7588 ,4);
push(&pq, 2025 ,1);
push(&pq, 6069 ,3);
push(&pq, 2025, 3);

   while (!isEmpty(&pq))
   {
       cout << " " << peek(&pq);
       pop(&pq);
   }
   return 0;
}