Question

develop a java program using linkedlist to implement priority queue ADT with following operations:

void insert(double priority);

int delete_min();

public boolean isEmpty();

double findMin();

double deleteMin()

EmptyPQException()

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// PriorityQueue.java

public class PriorityQueue {

      // Node pointers to head and tail of the queue

      private Node headNode;

      private Node tailNode;

      // method to insert a node in proper position so that the queue will always

      // be in sorted order, and minimum value will be in headNode

      public void insert(double priority) {

            Node newNode = new Node(priority);

            // checking if headNode is null (empty list - case 1)

            if (headNode == null) {

                  // adding as both head node and tail node

                  headNode = newNode;

                  tailNode = newNode;

                  // returning from function

                  return;

            }

            // checking if new element could be added before current head node (case

            // 2)

            if (newNode.priority < headNode.priority) {

                  // adding before head node and updating head node

                  newNode.next = headNode;

                  headNode = newNode;

                  return;

            }

            // taking a reference to first two nodes

            Node current = headNode;

            Node nextNode = headNode.next;

            // looping and checking if the element can be added in between any pairs

            // of node (case 3)

            while (nextNode != null) {

                  if (newNode.priority >= current.priority

                              && newNode.priority <= nextNode.priority) {

                        // new node can be added between current and next node

                        newNode.next = nextNode;

                        current.next = newNode;

                        return;

                  }

                  // advancing to next pair of nodes

                  current = nextNode;

                  nextNode = current.next;

            }

            // at the end, if the new node is still not added, adding to tail (case

            // 4)

            tailNode.next = newNode;

            tailNode = newNode;

      }

      // returns true if queue is empty

      public boolean isEmpty() {

            return headNode == null;

      }

      // returns the minimum value in the queue

      public double findMin() throws EmptyPQException {

            // throwing exception if empty

            if (isEmpty()) {

                  throw new EmptyPQException();

            }

            // according to our insert method, minimum value will always be in the

            // head node

            return headNode.priority;

      }

      // method to delete the minimum value from the queue

      public double deleteMin() throws EmptyPQException {

            if (isEmpty()) {

                  throw new EmptyPQException();

            }

            // storing value of head node

            double priority = headNode.priority;

            // advancing head node

            headNode = headNode.next;

            // making tail node null if head node became null

            if (headNode == null) {

                  tailNode = null;

            }

            // returning removed value

            return priority;

      }

}

// class to represent a Node in the queue

class Node {

      double priority;

      Node next;

      public Node(double priority) {

            this.priority = priority;

            next = null;

      }

}

// class for handling Exception when PriorityQueue is empty

class EmptyPQException extends Exception {

      public EmptyPQException() {

            super("Priority Queue is empty!");

      }

}

//Test.java (a class for testing PriorityQueue)

public class Test {

      public static void main(String[] args) throws EmptyPQException {

            // creating a PriorityQueue

            PriorityQueue queue = new PriorityQueue();

            // adding some values

            queue.insert(12.5);

            queue.insert(1.2);

            queue.insert(17);

            queue.insert(-2);

            queue.insert(15);

            queue.insert(1.7);

            queue.insert(8);

            queue.insert(2);

            queue.insert(9);

            // continuously removing the min value from the queue until it is empty

            while (!queue.isEmpty()) {

                  //displaying min value

                  System.out.println(queue.findMin());

                  //removing min value

                  queue.deleteMin();

            }

      }

}

/*OUTPUT*/

-2.0

1.2

1.7

2.0

8.0

9.0

12.5

15.0

17.0