Unsorted Insert List implementation of Priority Queue Rewrite implementation of

ID: 3564839 • Letter: U

Question

Unsorted Insert List implementation of Priority Queue

Rewrite implementation of priority queue given in class PriorityQueueL.java with List defined as

    private int count;
    private List itemList;

(see List.java), so that it uses this unsorted, non-recursive metod insert (it is mandatory thet you use this code with no modifications)

    public void insert(int newItem)
    {
        cnt.incr();
        List N = new List();
        N.head=newItem;
        N.tail=itemList;
        itemList=N;
        count++;
    }

and appropriately modified remove() method that removes the largest element from the priority queue passed to it as the implicit argument.

You may need to implement a method that finds the largest element in a List defined above, first.

After the above modifications, your class PriorityQueueL.java must work as needed when invoked by the sorting method included in class PriorityQueueTestL.java.

In particular, both the sorting and the values of T(n) must be correct.

You are supposed to add to your program any other classes (for instance, cnt.java) that might be necessary; you may re-use them from previous projects if appropriate.

PriorityQueueL.java

--- computed results by your program for arrays (to be sorted) of sizes from 1 to 20, each of which including increasigly sorted, decreasingly sorted, and pseudo-random array, just like the code in classPriorityQueueTestL.java is designed to do.

Explanation / Answer

public class ListQueue<T> implements Queue<T>
{ private class QueueNode
 { public T data;
 public QueueNode next;
 } // inner class QueueNode

    /** Reference to the head (front) of the queue.
      */
    private QueueNode hd;
    /** Reference to the tail (back) of the queue.
      */
    private QueueNode tl;

/** Create an empty queue.
 * Postcondition: The queue is empty.
 */
 public ListQueue ()
 { hd = tl = null; }

/** Add an item to the tail of a queue.
 * Postcondition: The queue is not empty.
 * @param item The item to be added to the queue.
 */
 public void add (T item)
 { QueueNode newNode = new QueueNode();
 newNode.data = item;
 newNode.next = null;
 if (tl != null)
 tl.next = newNode;
 tl = newNode;
 if (hd == null) // First item in queue
 hd = tl;
 } // add

/** Remove an item from the head of a queue.
 * Precondition: The queue is not empty.
 * Postcondition: The item at the head of the queue is removed and returned.
 * @return The item from the head of the queue.
 * @throws Assertionerror If the queue is empty.
 */
 public T remove ()
 { assert hd != null;
 T tmpData = hd.data;
 hd = hd.next;
 if (hd == null) // Was last element
 tl = null;
 return tmpData;
 } // remove

/** Return a copy of the item at the head of a queue.
 * Precondition: The queue is not empty.
 * @return The value of the item at the head of the queue.
 * @throws Assertionerror If the queue is empty.
 */
 public T head ()
 { assert hd != null;
 return hd.data;
 } // head

/** Tell if a queue contains any items.
 * @return <CODE>true</CODE> if there are no items in the queue, otherwise <CODE>false</CODE>.
 */
 public boolean isEmpty ()
 { return hd == null;
 } // isEmpty

} // class ListQueue

Navigate

Unsigned and Signed Integers 4. Suppose we are designing a computer system and n

Unsorted Insert List implementation of Priority Queue Rewrite implementation of

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

Unsorted Insert List implementation of Priority Queue Rewrite implementation of

Question

Explanation / Answer

Related Questions

Navigate