Priority queue

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

		}

	}

}

CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.