Priority queue java source code

CS 111 Project 2 Priority Queue Spring 2020 I NSTRUCTIONS Complete the project detailed in this document using valid, executable Java code. Submit your work (including only the .java source code files indicated with in the specification below) to your lab instructor via eCampus no later than the deadline on the course calendar. At the top of every file you submit, include a comment with your full name and the tracking code 2001-111-2 for instructor use. Your work is compared to the work of your peers and online sources to detect plagiarism. L EARNING G OALS The goal of this project is to reinforce key concepts of lists, queues, reference-based structures, interfaces, and algorithm analysis. It is also intended to reinforce the skills needed to create and test a non-executable black box implementation of an ADT. S PECIFICATION You are given an interface PriorityQueue (the source code is at the end of this document) that specifies the protocols for a priority queue with generic values and generic discrete priorities. Implement the class DataStructurePQ implements PriorityQueue to fulfill the requirements of the interface (see the comments in the interface’s source code). When naming the class, fill in the DataStructure part of the name based on the data structure used. You may use any suitable implementation discussed in lecture, such as the SelfOrganizingListPQ or the ListOfQueuesPQ. You can ask an instructor for recommendations or approval for alternative implementations. You must write all your own code from scratch, although you may reuse any suitable code you wrote for a lab assignment in this course this semester. Other than the array, you may not use any data structures built into the Java API or any other API. For each constructor and method in your implementation, include a detailed comment analyzing the runtime in 𝑂(… ) notation. All operations must run in linear time or better, but any operation that can be implemented in constant time must be. N OTES You are not expected to implement a main method, and any main method you do submit may be ignored when grading. The class you implement is just an abstract data type, which you test as necessary using techniques discussed in lecture and lab. Do not change the PriorityQueue interface because any submitted copies are discarded. The instructors use their own copies of that interface as given. Your work is expected to integrate with the given interface without any conflicts. G RADING R UBRIC You are graded on 1) the correctness of your implementation of the requirements in the specification above and 2) the accuracy of your runtime analysis and attention to efficiency. The lab instructor determines the exact grading rubric to assess your performance and may provide unit tests for your convenience. I NTERFACE See the following page for the interface PriorityQueue source code. rev. March 21 – 1 / 2 I NTERFACE public interface PriorityQueue { /** * Clears or initializes the sequence of discrete priorities, * ordered from highest priority to lowest priority. * * Each constructor must call this method exactly once. */ void clearPriorities(); /** * Appends a new lowest priority to the priorities sequence. * * This method must be called after the clear operation is called * but before any value accessors or mutators are called. * @param priority The priority to append */ void appendPriority(P priority); /** * Adds a new value with a given priority behind * all other values with the same or higher priority * and before all values with a lower priority. * @param value A value to add * @param priority A priority for the value */ void enqueue(V value, P priority); /** * Removes the oldest value with the highest priority. * @return The value to be removed */ V dequeue(); /** * Accesses the oldest value with the highest priority. * @return The value to be accessed */ V peek(); /** * Determines whether the priority queue has no values. * @return Whether the priority queue is empty */ boolean isEmpty(); /** * Neatly represents the values in the priority * queue in descending order of priority with both * their values and priorities. */ String toString(); } 2/2 ...