ap
Interface PriorityQueue

All Known Implementing Classes:

ArrayPriorityQueue, HeapPriorityQueue

public interface PriorityQueue

The interface for priority queues as they will be used on the Advanced Placement Computer Science exam. Exam questions may use the PriorityQueue interface as the type for parameters, variables, and fields. Consider the question below which asks to remove all items from a priority queue that are smaller than a specified limit and the code for the answer. The question can be answered using just the PriorityQueue interface.

Write the function removeLessThan that removes all items in parameter pq that are strictly less than parameter limit. Assume all items stored in pq implement the Comparable interface.

 // Removes all items less than limit from pq

 public static void removeLessThan(PriorityQueue pq, Comparable limit)
 {
     while (! pq.isEmpty() && limit.compareTo(pq.peekMin()) > 0) {
         pq.removeMin();
     }
 }
 

Note: there is no method size to return the number of elements stored in a priority queue, the AP subset/interface doesn't include such a method.

Method Summary

void	add(java.lang.Object x) Adds an item to this priority queue.
boolean	isEmpty() Returns true if this stack is empty, otherwise returns false.
java.lang.Object	peekMin() Returns the smallest item stored in this priority queue without removing it.
java.lang.Object	removeMin() Removes and returns the smallest item stored in this priority queue.

Method Detail

isEmpty

public boolean isEmpty()

Returns true if this stack is empty, otherwise returns false.

Returns:

true if this stack is empty, otherwise return false.

add

public void add(java.lang.Object x)

Adds an item to this priority queue.

Parameters:

x - is the object added to this priority queue

removeMin

public java.lang.Object removeMin()

Removes and returns the smallest item stored in this priority queue.

Returns:

the smallest item stored in this priority queue

Throws:

java.lang.RuntimeException - if the priority queue is empty (unchecked)

peekMin

public java.lang.Object peekMin()

Returns the smallest item stored in this priority queue without removing it.

Returns:

the smallest item stored in this priority queue

Throws:

java.lang.RuntimeException - if the priority queue is empty (unchecked)