Below is a queue interface and a priority queue class, with tests.
/**
* A collection that typically stores its elements in a FIFO
* (first-in-first-out) manner
* Modeled after Queue interface in the Java Collections Framework
*
* @author Elena Machkasova for CSCi 2101
*
* @param <E> - the type of elements it holds
*/
public interface OurQueue<E> extends Iterable<E> {
/**
* Returns the number of elements in this queue.
*
* @return the size of the queue
*/
public int size();
/**
* Returns true if this collection contains no elements, false
* otherwise.
*
* @return true if this collection contains no elements, false
* otherwise.
*/
public boolean isEmpty();
/**
* Retrieves, but does not remove, the head of this queue.
* Throws an exception if this queue is empty.
*
* @return the head of this queue.
* @throws NoSuchElementException - if this queue is empty.
*/
public E element();
/**
* Adds an element to the end of the queue
*
* @param element - the element to be added to the queue
*/
public void add(E element);
/**
* Retrieves and removes the head of this queue.
* Throws an exception if this queue is empty.
*
* @return the head of this queue
* @throws NoSuchElementException - if this queue is empty.
*/
public E remove();
/**
* Removes all of the elements from this queue making it empty.
*/
public void clear();
}
import java.util.NoSuchElementException;
public class TestPriorityQueue {
public static void main(String [] args) {
OurQueue<String> queue = new OurPriorityQueue<String>();
System.out.println(queue.isEmpty()); // expect true
System.out.println(queue.size()); // expect 0
queue.add("kiwi");
System.out.println(queue.isEmpty()); // expect false
System.out.println(queue.size()); // expect 1
System.out.println(queue.element()); // expect "kiwi"
queue.add("apple");
queue.add("orange");
// expect apple, kiwi, orange
for (String fruit: queue) {
System.out.println(fruit);
}
System.out.println(queue.isEmpty()); // expect false
System.out.println(queue.size()); // expect 3
System.out.println(queue.element()); // expect "apple"
System.out.println(queue.remove()); // expect "apple"
System.out.println(queue.size()); // expect 2
System.out.println(queue.element()); // expect "kiwi"
System.out.println(queue.remove()); // expect "kiwi"
System.out.println(queue.size()); // expect 1
System.out.println(queue.remove()); // expect "orange"
System.out.println(queue.isEmpty()); // expect true
System.out.println(queue.size()); // expect 0
try {
queue.element();
} catch (NoSuchElementException e) {
System.out.println(e.getMessage());
}
}
}
/**
*
* The class implements a min-priority queue, i.e. smaller numbers
* have higher priority. For instance, if the queue contains
* 2, 4, 1, then 1 is returned first, then 2, then 4.
* The smallest element in the queue is called the head of the queue.
* If the queue contains several elements with the same minimal value,
* any one of them may play the role of the head.
*
* Elements inserted in the the queue must implement Comparable interface.
* They are ordered based on the ordering determined by their
* compareTo method.
*
* @param <E> - type of elements in the queue. Must implement Comparable<E>
*/
import java.util.Iterator;
public class OurPriorityQueue<E extends Comparable<E>> implements OurQueue<E> {
private Node first;
private int size;
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return (first == null);
}
@Override
public E element() {
// TODO Auto-generated method stub
return null;
}
@Override
public void add(E item) {
if(first == null || item.compareTo(first.item) < 0) {
first = new Node(item, first);
size++;
}
//Node newNode = new Node(item, null);
}
@Override
public E remove() {
// TODO Auto-generated method stub
return null;
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public Iterator<E> iterator() {
return new PriorityQueueIterator();
}
private class Node {
public E item;
public Node next;
public Node(E newItem, Node nextNode) {
item = newItem;
next = nextNode;
}
}
private class PriorityQueueIterator implements Iterator<E> {
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
@Override
public E next() {
// TODO Auto-generated method stub
return null;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
}