QuestionQuestion

Complete the project detailed in this document using valid, executable Java code.

You are given an interface PriorityQueue<V, P> (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<V, P> implements PriorityQueue<V, P> 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 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.

INTERFACE:
public interface PriorityQueue<V, P> {
       /**
}

* 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();

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class SelfOrganizingListPQ<V, P> implements PriorityQueue<V, P> {

    Node head;
    PNode phead;
    PNode ptail;

    int size;
    int pnodeCounter;

    private class PNode {

       PNode next;
       int order;
       P priority;

       public PNode(int order, P priority) {
            next = null;
            this.order = order;
            this.priority = priority;
       }

    }

    private class Node {

       Node next;
       V value;
       int order;
       P priority;

       public Node(V value, int order, P priority) {
            this.next = null;
            this.value = value;
            this.order = order;
            this.priority = priority;
       }

    }

    public SelfOrganizingListPQ() {
       // Runtime:
       clearPriorities();
    }

    public static void main(String[] args) {
       PriorityQueueTester.test(new SelfOrganizingListPQ<String, String>());
    }

    @Override
    public void clearPriorities() {
       // Runtime:
       head = null;
       size = 0;
       phead = null;
       ptail = null;

       pnodeCounter = 0;
    }

    /**
    * 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
    */
    @Override
    public void appendPriority(P priority) {
       // Runtime:
       // set the lower priority
       PNode pn = new PNode(pnodeCounter, priority);
       pnodeCounter++;

       if (phead == null) {
            phead = pn;
            ptail = pn;
       } else {
            ptail.next = pn;
            ptail = pn;
       }

    }...
$20.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats