HW#8 SPECS: PRIORITY QUEUE, USING AN ORDERED ARRAY =============================
ID: 3767742 • Letter: H
Question
HW#8 SPECS: PRIORITY QUEUE, USING AN ORDERED ARRAY ====================================== Hint: HW8 is somewhat similar to the "insertion sort" routines that we discussed in recent weeks. As in prior lecture discussions: * a "queue" is like a movie line -- the first person in, is the first person out * a "priority queue" is similar, but higher-priority items can "cut" in line -- that is, they walk from the back of the line to the front of the line, but must stop if they come to an item that has the same priority or higher priority. SUBMITTING YOUR CODE: This assignment requires coding at least two classes: Item, and CustomPQ. All classes MUST be in a single file, named CustomPQ.java. By the rules discussed earlier in the semester, this will require you to cut the word "public" from the other classes in your file: public class CustomPQ { ... } class Item { ... } This is the type of single file that you must submit for HW8. (Of course, you will probably want to create a separate Prog1.java tester program, when testing your code, but do NOT submit your tester program for HW8.)
PART 1. CREATE A PRIORITY QUEUE "ITEM" CLASS --------------------------------------------
An item in a "priority queue" has two things: * the data * a priority value Create an Item class, which has two instance variables (properties): * info -- of type int (int for ease) * p -- priority, of type int. Priority values are 1-10, with lower numbers = higher priority. (For ease, you do NOT need to enforce the legal range, 1-10, you can assume that Prog1 testers will always use legal ranges.) The Item class has a compareTo routine, to make comparisons easier: * compareTo -- compares Item priorities. Specifically, obj1.compareTo(obj2) will return: * -1 if obj1 is "LESS THAN" obj2, as per Java's rules, but "less than" IN TERMS OF PRIORITY (so, its p has a HIGHER int value). * 0 if obj1 is "equal to" obj2, meaning their priority p's are equal. * 1 if obj1 is "GREATER THAN" obj2, as per Java's rules, but "greater than" IN TERMS OF PRIORITY (so, it's p has LOWER int value). NOTE: DO NOT USE ARRAYS.SORT FOR HW8 -- *YOU MUST CODE THE PROPER INSERTIONS! The compareTo is just to assist you with that task. PART
2. PRIORITY QUEUE, USING AN ORDERED ARRAY ---------------------------------------------- Create a CustomPQ class. It has the usual enqueue and dequeue routines, but, as with all priority queues, a new item can cut to the front until it encounters an item with same or higher priority. To keep track of the items, use an array. Hint: Your CustomPQ objects each get an array of Items. (For ease, assume array size 100, and assume the user will never insert more than 100 items. Also, you will NOT need to use the "%" efficiency tricks from the "array queue" lectures.) The data-tracking array must be ordered, which means: the items in the array exactly match what the "line" looks like -- that is, the highest priority items are at the left/front of the array, the lowest priority items are at the right/back of the array. So, a dequeue simply takes out the front item (highest-priority item). But, the enqueue must calculate where each new item must get inserted into the array, then must shift the array's items to fit it there. When a Prog1 tester program uses the priority queue's enqueue, the Prog1 will specify the item to insert by using two int properties as parameters, NOT by creating an Item object: an int parameter for the info, and an int parameter for the p. See sample Prog1 below. When a Prog1 tester program uses the priority queue's dequeue, it will get the proper item's info, NOT the priority p. See sample Prog1 below. ---------------------------------------------------------------------- SAMPLE PROG1, TO TEST YOUR PROGRAMS =================================== public class Prog1 { public static void main(String args[]) { CustomPQ q = new CustomPQ(); q.enqueue( 100 , 5 ); //sets up: 1000 , 99 , 100 , 80 , 101 , 80 q.enqueue( 101 , 10 ); // 1 1 5 6 10 10 q.enqueue( 80 , 10 ); q.enqueue( 80 , 6 ); q.enqueue( 1000 , 1 ); q.enqueue( 99 , 1 ); //ex: item's info is 99, p is 1 for (int i=1; i<=6; i++) { int r = q.dequeue(); System.out.println(r); } } } PROGRAM'S CORRECT OUTPUT IS: ---------------------------- 1000 99 100 80 101 80 --------------------------------
Explanation / Answer
//Program:
package prog1;
class item
{
int info;
// Priority values are 1-10, with lower numbers = higher priority.
int priority;//
int compareTo(item obj2)
{
if(this.compareTo(obj2)<0)// lower priority, higher priority value
return -1;
else if(this.compareTo(obj2)>0) //higher priority, lower priority value
return 1;
else
return 0;// equal priority
}
}
class CustomPQ {
item items[];
int size;
public CustomPQ()
{
items=new item[100];
size=0;
}
void enqueue(int info, int priority) {
for(int i=0;i<=size;i++)
{
int v=items[i].compareTo(items[0]);
if(v==0)
{
for(int j=1;j<=size;j++)
{
items[j+1]=items[j];
}
items[1].info=info;
items[1].priority=priority;
}
else if(v==1)
{
for(int j=0;j<=size;j++)
{
items[j+1]=items[j];
}
items[0].info=info;
items[0].priority=priority;
}
else
{
items[size+1].info=info;
items[size+1].priority=priority;
}
}
size++;
}
int dequeue() {
int dat=items[0].info;
size--;
return dat;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.