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()
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
develop a java program using linkedlist to implement priority queue ADT with following operations: void insert(double...
JAVA Implement a MyQueue class which implements a queue using two stacks. private int maxCapacity = 4; private Stack stack1; private Stack stack2; Note: You can use library Stack but you are not allowed to use library Queue and any of its methods Your Queue should not accept null or empty String or space as an input You need to implement the following methods using two stacks (stack1 & stack2) and also you can add more methods as well: public...
In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to...
Write a program in Java to implement the max-priority queue using max-heap data structure. Implement the max-heap data structure using an integer array of 10 cells. (Do not use Java in-built PriorityQueue class.) [In a max-heap, the root node and the intermediate node vales are always greater than their children.] First, take 10 integer values from the user and insert them in the max-priority queue. Then print the elements of the queue. After that, delete two elements from the queue...
Design and implement a class Q that uses Q.java as a code base. The queue ADT must use class LinkedList from Oracle's Java class library and its underlying data structure (i.e. every Q object has-a (contains) class LinkedList object. class Q is not allowed to extend class LinkedList. The methods that are to be implemented are documented in Q.java. Method comment blocks are used to document the functionality of the class Q instance methods. The output of your program must...
Collect/finish the Java code (interface and the complete working classes) from lecture slides for the for the following ADT: 3) Queue ADT that uses an array internally (call it AQueue) Make sure you keep the same method names as in the slides (automatic testing will be performed)! Make sure your classes implement the corresponding interfaces. Put your classes in a package called cse11. Try to make the code robust and try to use generics. The Queue ADT The Queue ADT...
java create java program that make stack with LinkedList and stack is implement iterator. When stack’s iterator call next(), it pop its data. here is the example of output //by user 5 1 2 3 4 5 //then output comes like this 5 4 3 2 1 Stack is empty. here is the code that i'm going to use class Stack<T> implements Iterator<T> { LinkedList<T> list; public Stack() { list = new LinkedList<T>(); } public boolean isEmpty() { return list.isEmpty(); ...
Polynomial Using LinkedList class of Java Language Description: Implement a polynomial class using a LinkedList defined in Java (1) Define a polynomial that has the following methods for Polynomial a. public Polynomial() POSTCONDITION: Creates a polynomial represents 0 b. public Polynomial(double a0) POSTCONDITION: Creates a polynomial has a single x^0 term with coefficient a0 c. public Polynomial(Polynomial p) POSTCONDITION: Creates a polynomial is the copy of p d. public void add_to_coef(double amount, int exponent) POSTCONDITION: Adds the given amount to...
Comparing the insertion and removing performance between ALPQueue with HeapPQueue. Requirements: 1/ Task1: implement a concrete ALPQueue class (an ArrayList based priority queue) that extends the AbstractPQueue discussed in the class, along with PQueue.java, ArrayList.java, List.java, PQEntry.java , EntryComparitor.java, and OutOfRangeException.java given in the class (any other implementation of above classes that are not compatible with List interface and AbstractPQueue class will not receive any credit). 2/ Task2: implement a concrete HeapPQueue class (a Heap based priority queue) that extends...
Create a Java code that includes all the methods from the Lecture slides following the ADTs LECTURE SLIDES Collect/finish the Java code (interface and the complete working classes) from lecture slides for the following ADTS: 4) Queue ADT that uses a linked list internally (call it LQueue) Make sure you keep the same method names as in the slides (automatic testing will be performed)! For each method you develop, add comments and estimate the big-O running time of its algorithm....
Using Java coding, complete the following: This program should implement a LinkedList data structure to handle the management of student records. It will need to be able to store any number of students, using a Linked List. LinearNode.java can be used to aid creating this program Student should be a class defined with the following: • String name • int year • A linked list of college classes (college classes are represented using strings) • An...