CS 231 Lab 7

Priority Queues

A priority queue is a dynamic data structure that always returns the entry in the queue with the highest priority. The lab this week is to create a priority queue based on a LinkedList data structure.

Here are the links to the API's for the most recent versions of Java:


Tasks

  1. Create a new generic class MyPriorityQueue<T> that implements Iterable<T>. You can call it whatever you like, but PriorityQueue is a standard class in Java, so don't use that. As before, create a Node class that can hold something of the generic type T and a next pointer.
  2. Either copy from your singly-linked LinkedList or just create a new implementation of the following methods using a singly-linked list structure. Note that, in addition to a head pointer and a counter, you will need a variable to hold the maximum size of the queue and a variable to hold a Comparator object.

    • public MyPriorityQueue( int maxsize, Comparator<T> comp ) - constructor that takes in the max size of the queue and a Comparator object that can be used to compare two elements of the queue.
    • boolean add( T item ) - adds the item to the queue. You can either shove it on the front or keep the list ordered. Keeping the list ordered saves work in other functions such as getNext, remove, and toString. If the queue is full and it is not possible to add the item, then it return false. Otherwise, it returns true.
    • void clear() - clears the queue.
    • T getNext() - returns a reference to the highest priority element in the queue.
    • int getSize() - returns the current size of the queue.
    • boolean isEmpty() - returns true if the queue is empty.
    • boolean isFull() - returns true if the queue is full.
    • T remove() - removes the item with highest priority given the Comparator.
    • String toString() - generate some text representation of the queue.
    • ArrayList toArrayList() - return an ArrayList of the elements in the queue.
    • void setComparator(Comparator comp) - takes in a Comparator object that can compare to elements of type T and uses it for all future priority comparisons. Note that this function may need to re-order the existing elements in the queue.

  3. Implement an iterator for the priority queue so it can implement the Iterable interface. The iterator does not need to traverse the elements in priority order (although it should).

When you are finished, you can run this test-bench file to see if your Priority Queue is working.

When you are ready, move on to this week's project.