CSC1020 Homework 7

Overview

The Queue interface in Java defines a number of methods to access, add, and remove items from a queue structure, maintaining FIFO by adding at the end of the queue and removing from the beginning of the queue. We are going to implement the Queue interface, but rather than implement a traditional queue we are going to, by changing the way elements are added to the queue, create a PriorityQueue.

PriorityQueue

A PriorityQueue is a structure that adds elements to a Queue, but stores these elements in some order, usually based on a data value contained in the element. Polling the PriorityQueue returns the first element in the queue, as usual, but it is not necessarily FIFO. An example would be if we had a PriorityQueue that stored Integer objects, the queue would be sorted low to high, so the following code:

PriorityQueue nums = new PriorityQueue<>();
nums.add(5);
nums.add(3);
System.out.println(nums.poll());

would print “3”.

When implementing a PriorityQueue, there are two things that need to change from a regular Queue:

1. must be Comparable

There is a requirement that any Object type assigned to an element in the PriorityQueue must be able to be compared with other elements, otherwise there will be no way to keep the queue ordered. To ensure that when defining the PriorityQueue in the header you need to specify that any generic type E must implement the Comparable interface using the following structure:

<E extends Comparable<? super E>

This states that any type declared in the class must either implement the Comparable interface itself or inherit from some superclass that does.

The Comparable Interface

The Comparable interface has a single abstract method, compareTo(T o) that compares the given object to a second object that has been passed in as a parameter and returns:

-1	if the given object is “less than” the second object
 0	if the given object and the second object are equal
 1	if the given object is “greater than” the second object

“less than” and “greater than” can be numeric, alphabetical, or any ordering that is defined within the compareTo() method. Strings, for example, compare the ASCII values of the characters in the String.

2. Add/Offer

The add() and offer() methods will compare the element being added to the existing elements in the queue, using the Comparable interface’s compareTo() method, and insert the element in the appropriate location relative to the existing elements. If two elements are equal, the new element is inserted after the existing element. If there are multiple existing elements that are equal, the new element will always be added after all of the existing elements of the same value.

Requirements

• Complete the partial implementation of the SJQueue with the following restrictions:

  • Use a LinkedList as the backing data structure
  • You may ignore any methods that throws an UnsupportedOperationException
  • Carefully follow the java docs provided
    • Verify that the proper exceptions are being caught, thrown, and handled.
      • Do not catch and re-throw an exception generated by your backing data structure unless you need to change the exception type.

• Write a new PriorityQueue class that inherits from SJQueue

  • The PriorityQueue should only accept objects that can be compared using the Comparable interface
  • You should only override the add() and offer() methods. The rest of the inherited methods should remain the same.
    • These methods will be functionally the same, as our backing data structure does not have a fixed capacity, but both are expected to operate identically. so they both must be implemented

• Write a JUnit test suite that tests the add() and offer() methods of your PriorityQueue with following boundary conditions:

  • adding a null element to the queue
  • adding to an empty queue
  • adding to a queue with one other (different) element
  • adding to a queue with multiple (different) elements
  • adding to a queue with multiple elements where exactly one existing element is the same as the element being added
  • adding to a queue with multiple elements where several existing elements are the same as the element being added

• Use an existing type that implements Comparable, such as a String, Integer, or Double.

• You may use the SJQueues toArray() method to assist with testing. Be aware that toArray() returns an Object array, so you may need to typecast your results.