Linked Queue With Priorty Your assignment is to write a Java program that manage

Question

Linked Queue With Priorty

Your assignment is to write a Java program that manages a linked queue where the items in the queue have a priority. The head of the queue points to the first entry on the queue which is the entry with the highest priority. The first entry points to the 2nd node (or is null if the list is empty) which is the entry with the 2nd highest priority, etc. The last entry will point to null. Each node on the queue will have two parts, the pointer to the next entry on the queue (or null) and a pointer to the data item associated to that node entry (which should never be null). The data items are very simple and will consist of two parts, a priority which is a number from 0 to 100 inclusive with 100 being the highest and 0 being the lowest priority and a string.

You will need to create the following methods:

enqueue(newEntry): boolean Adds an entry to the proper place in the queue given its priority. Returns false if cannot addan entry and true if the addition was successful.

dequeue(): T Removes and returns the entry with the highest priority (the 1st entry on the queue).

isEmpty(): boolean Detects whether the queue is empty (true if yes, otherwise false).

clear(): void Removes all entries from the queue.

length(): int Returns the length of the queue.

returnArray(): array T Returns an array of all the entries on the queue in priority order (not nodes, just the data).

main(): void This will probably be the hardest method. It needs to have code that demonstrates that all of the other methods work.

Notes:

Do not use the Java built in list methods, create your own.

Assume that all initialization has been done.

Assume that a call to dequeue will always find something in the queue.

No restriction is placed on the length of the queue.

Feel free to steal code from the book.

Put all methods in a single “.java” file.

Explanation / Answer

import java.util.Scanner;

/** Class PriorityQueue **/
class PriorityQueue {
   private Task[] heap;
   private int heapSize, capacity;

   /** Constructor **/

   public PriorityQueue(int capacity) {
       this.capacity = capacity + 1;
       heap = new Task[this.capacity];
       heapSize = 0;
   }

   /**
   * @return array
   */
   public Task[] toArray() {

       return heap;
   }

   /** function to clear **/
   public void clear() {
       heap = new Task[capacity];
       heapSize = 0;
   }

   /** function to check if empty **/
   public boolean isEmpty() {
       return heapSize == 0;
   }

   /** function to check if full **/
   public boolean isFull() {
       return heapSize == capacity - 1;
   }

   /** function to get Size **/
   public int size() {
       return heapSize;
   }

   /** function to insert task **/
   public void insert(String job, int priority) {
       Task newJob = new Task(job, priority);

       heap[++heapSize] = newJob;
       int pos = heapSize;
       while (pos != 1 && newJob.priority > heap[pos / 2].priority) {
           heap[pos] = heap[pos / 2];
           pos /= 2;
       }
       heap[pos] = newJob;
   }

   /** function to remove task **/
   public Task remove() {
       int parent, child;
       Task item, temp;
       if (isEmpty()) {
           System.out.println("Heap is empty");
           return null;
       }

       item = heap[1];
       temp = heap[heapSize--];

       parent = 1;
       child = 2;
       while (child <= heapSize) {
           if (child < heapSize
                   && heap[child].priority < heap[child + 1].priority)
               child++;
           if (temp.priority >= heap[child].priority)
               break;

           heap[parent] = heap[child];
           parent = child;
           child *= 2;
       }
       heap[parent] = temp;

       return item;
   }
}

/** class Task **/
class Task {
   String job;
   int priority;

   /** Constructor **/
   public Task(String job, int priority) {
       this.job = job;
       this.priority = priority;
   }

   /** toString() **/
   public String toString() {
       return "Job Name : " + job + " Priority : " + priority;
   }
}

/** Class PriorityQueueTest **/
public class PriorityQueueTest {
   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       System.out.println("Priority Queue Test ");

       System.out.println("Enter size of priority queue ");
       PriorityQueue pq = new PriorityQueue(scan.nextInt());

       char ch;
       /* Perform Priority Queue operations */
       do {
           System.out.println(" Priority Queue Operations ");
           System.out.println("1. insert");
           System.out.println("2. remove");
           System.out.println("3. check empty");
           System.out.println("4. check full");
           System.out.println("5. clear");
           System.out.println("6. size");
           System.out.println("7. Display");

           int choice = scan.nextInt();
           switch (choice) {
           case 1:
               System.out.println("Enter job name and priority");
               pq.insert(scan.next(), scan.nextInt());
               break;
           case 2:
               System.out.println(" Job removed " + pq.remove());
               break;
           case 3:
               System.out.println(" Empty Status : " + pq.isEmpty());
               break;
           case 4:
               System.out.println(" Full Status : " + pq.isFull());
               break;
           case 5:
               System.out.println(" Priority Queue Cleared");
               pq.clear();
               break;
           case 6:
               System.out.println(" Size = " + pq.size());
               break;
          
           default:
               System.out.println("Wrong Entry ");
               break;
           }

           System.out.println(" Do you want to continue (Type y or n) ");
           ch = scan.next().charAt(0);
       } while (ch == 'Y' || ch == 'y');
   }
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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