It is very important that this problem will be solved by using Heaps and Priorit
ID: 641664 • Letter: I
Question
It is very important that this problem will be solved by using Heaps and Priority Queues. I only need solution where we use heaps.
There is only one printer. The instructor, the TA and students all sent their print jobs to this one printer.The print jobs were not done first in, first out (a queue).
Accordingly, student jobs were done first in, first out. But all TA print jobs were done before any student print job, with the TA's print jobs being done first in, first out. And you guessed it -- All instructor print jobs were done before any TA print job, with the instructor's print jobs being done first in, first out.
Your Task
Your job is to write the software to manage the printer queue. To do so, you must use Heaps and Priority Queues.
The program will display a menu and prompt the user to enter a choice:
Printer queue
=========
1. Add job
2. Print job
3 View jobs
4. Exit
Enter choice:
You may assume the user enters 1, 2, 3 or 4. No input validation is required.
If the user chooses 4. Exit, then the program ends. The following discusses the other 3 choices.
Add Job
If the user chooses Add job, then the program asks the user who is requesting the job:
Instructor (I or i)
TA (T or t)
Student (S or s)
You may assume that the the user enters I, i, T, t, S or s. No input validation is necessary.
The program then adds the print job to the priority queue. The data added reflects who the job is for (instructor, TA or student) and the number of the print job (an incrementing number, starting with 1, then 2, 3, 4, etc.). Hint: You may want to sue a structure.
Print Job
If the user chooses Print job, if there are any print jobs in the queue, then the program outputs, for the highest priority print job, who the job is for (instructor, TA or student) and the number of the print job. That print job also is removed from the priority queue. However, if there are no print jobs in the queue, then the program outputs: "No print jobs in queue."
View Jobs
If the user chooses Print job, then the program outputs, for each print job in the queue, and in order of priority, who the job is for (instructor, TA or student) and the number of the print job. However, if there are no print jobs in the queue, then the program outputs: "No print jobs in queue."
Number of Jobs
You could use a vector and just allocate elements dynamically. But if you want to use an array, you can choose a large number so you don't run out of job numbers.
heap.h - declaration file for heap.
heap.cpp - implementation file for heap.
pqtype.h - declaration file for priority queue.
pqtype.cpp - implementation file for priority queue.
test.cpp - driver file.
Sample Input/Output
Here is sample input/output. After the first menu output, I have [menu output] instead of displaying the menu again to shorten the sample input/output.
Printer queue
=========
1. Add job
2. Print job
3. View jobs
4. Exit
Enter choice: 3
No print jobs in queue.
[menu output]
Enter choice: 2
No print jobs in queue.
[menu output]
Enter choice: 1
Instructor (I or i), TA (T or t), or Student (S or s)? s
[menu output]
Enter choice: 3
job #1: Student
[menu output]
Enter choice: 1
Instructor (I or i), TA (T or t), or Student (S or s)? i
[menu output]
Enter choice: 3
job #2: Instructor
job #1: Student
[menu output]
Enter choice: 1
Instructor (I or i), TA (T or t), or Student (S or s)? t
[menu output]
Enter choice: 3
job #2: Instructor
job #3: TA
job #1: Student
[menu output]
Enter choice: 1
Instructor (I or i), TA (T or t), or Student (S or s)? i
[menu output]
Enter choice: 3
job #2: Instructor
job #4: Instructor
job #3: TA
job #1: Student
[menu output]
Enter choice: 2
Now printing job #2: Instructor
[menu output]
Enter choice: 3
job #4: Instructor
job #3: TA
job #1: Student
[menu output]
Enter choice: 2
Now printing job #4: Instructor
[menu output]
Enter choice: 3
job #3: TA
job #1: Student
[menu output]
Enter choice: 2
Now printing job #3: TA
[menu output]
Enter choice: 3
job #1: Student
[menu output]
Enter choice: 2
Now printing job #1: Student
[menu output]
Enter choice: 3
No print jobs in queue.
[menu output]
Enter choice: 2
No print jobs in queue.
[menu output]
Enter choice: 4
Press any key to continue . . .
Explanation / Answer
Program code:
#ifndef pqtype
#define pqtype
#include "heap.h"
#include <string>
using namespace std;
// node of the Priority Queue
struct queue
{
//Declare variables
int priority;
int snumber;
string jobName;
queue *next;
};
//PriorityQueue
class PriorityQueue
{
private:
queue *front;
//constructor
public:
PriorityQueue()
{
front=NULL;
}
void PriorityQueue::addJob(string item, int priority, int number);
void PriorityQueue::printJob();
void PriorityQueue::viewJob();
};
#endif
#include "stdafx.h"
#include "pqtype.h"
#include <iostream>
void PriorityQueue::addJob(string item, int priority, int number)
{
queue *temp, *q;
temp = new queue;
temp->jobName = item;
temp->priority = priority;
temp->snumber = number;
//whether queue is empty
if (front == NULL || priority < front->priority)
{
temp->next = front;
front = temp;
}
else
{
q = front;
while (q->next != NULL && q->next->priority <= priority)
q=q->next;
temp->next = q->next;
q->next = temp;
}
}
void PriorityQueue::printJob()
{
queue *temp;
if(front == NULL)
cout<<"No print jobs in queue. ";
else
{
temp = front;
cout<<"Now printing Job # "<<temp->snumber<<" "<<temp->jobName<<endl;
front = front->next;
free(temp);
}
}
void PriorityQueue::viewJob()
{
queue *ptr;
ptr = front;
if (front == NULL)
cout<<"No print jobs in queue ";
else
{
while(ptr != NULL)
{
cout<<"Job #: "<<ptr->snumber<<" "<<ptr->jobName<<endl;
ptr = ptr->next;
}
}
}
#ifndef heap
#define heap
class Heap
{
public:
Heap()
{
heapSize=0;
}
void setSize(int size);
int parent(int i);
int left(int i);
int right(int i);
void heapify(int a[], int i);
void BuildMaxHeap(int a[]);
void HeapSort(int a[]);
int heapSize;
}
#endif
#include "stdafx.h"
#include "heap.h"
void Heap::setSize(int size)
{
heapSize=size;
}
int Heap::parent(int i)
{
if(i==1)
return 0;
if(i%2==0)
return ( (i / 2)-1);
else
return ( (i / 2));
}
int Heap::left(int i)
{
return (2 * i) + 1;
}
int Heap::right(int i)
{
return (2 * i) + 2;
}
void Heap::heapify(int a[], int i)
{
int l = left(i), great;
int r = right(i);
if ( (a[l] > a[i]) && (l < heapSize))
{
great = l;
}
else
{
great = i;
}
if ( (a[r] > a[great]) && (r < heapSize))
{
great = r;
}
if (great != i)
{
int temp = a[i];
a[i] = a[great];
a[great] = temp;
heapify(a, great);
}
}
void Heap::BuildMaxHeap(int a[])
{
for (int i = (heapSize - 1) / 2; i >= 0; i--)
{
heapify(a, i);
}
}
void Heap::HeapSort(int a[])
{
BuildMaxHeap(a);
for (int i = heapSize; i > 0; i--)
{
int temp = a[0];
a[0] = a[heapSize - 1];
a[heapSize - 1] = temp;
heapSize = heapSize - 1;
heapify(a, 0);
}
}
// Heaps and Priority.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
// Header file section
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include<string>
#include "pqtype.h"
#include "heap.h"
using namespace std;
int main()
{
//Declare variables
int choice,priority;
PriorityQueue pq;
Heap h;
char ch;
string jobName;
int number = 0;
cout<<"Printer queue"<<endl;
cout<<"============="<<endl;
do
{
//Prompt and read input from the user
cout<<" 1.Add Job ";
cout<<"2.Print Job ";
cout<<"3.View Job ";
cout<<"4.Exit ";
cout<<"Enter choice : ";
cin>>choice;
int *arr;
switch(choice)
{
//If the user chooses Add job, then the program asks the user
//who is requesting the job:
case 1:
cout<<"Instructor (I or i), TA (T or t), or Student (S or s)? ";
cin>>ch;
if(ch=='i' || ch =='I')
{
priority = 1;
jobName = "Instructor";
}
else if(ch=='t' || ch =='T')
{
priority = 2;
jobName = "TA";
}
else if(ch=='s' || ch =='S')
{
priority = 3;
jobName = "Student";
}
arr[number]=priority;
number++;
pq.addJob(jobName, priority,number);
h.setSize(number);
h.HeapSort(arr);
break;
case 2:
//Call the printJob method
pq.printJob();
for(int i=0;i<number;i++)
cout<<arr[i]<<" "<<endl;
break;
case 3:
//Call the viewJob method
pq.viewJob();
break;
case 4:
break;
default :
cout<<"Invalid choice. ";
}
}
//Exit the program
while(choice != 4);
//Pause the system for a while
system("PAUSE");
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.