QueuesS2C Home « Queues
In our final lesson on the different collection types within the Collection hierarchy we look at the PriorityQueue<E> concrete implementation of the Queue<E> interface.
So what type of collection is a Queue? A Queue is an ordered list of actions that are to be processed and as such does not allow null elements. Typically, a Queue would be in FIFO
(first-in, first-out) order although other orders such as LIFO (last-in, first-out), natural-ordering and custom comparator order are also possible.
Queue Hierarchy DiagramTop
The diagram below is a representation of the Queue hierarchy and covers the interfaces and class we will study in this lesson. The diagram has several interfaces and classes missing but should help in visualisation:
Queue Interfaces & ClassesTop
The table below gives a description of each interface and class within the above diagram:
| Interface/Class | Description |
|---|---|
Collection<E> | The root interface in the Collection hierarchy which the Queue<E> interface extends. There is no direct implementation of the Collection<E> interface within the JDK. |
Queue<E> | Interface for holding elements prior to processing. |
PriorityQueue<E> | Unbounded priority queue implementation of the Queue<E> interface that
based on a priority heap that does not permit null elements. |
Queue Types and OrderingTop
The table below extrapolates the commented information about ordering from the diagram above into a more readable tabular format:
| Collection Type | Ordering | |
|---|---|---|
| Queue | Ordered | Sorted |
PriorityQueue<E> | Sorted | PIPO (priority-in, priority-out) |
PriorityQueuesTop
A PriorityQueue is a sorted, ordered implementation of the Queue<E> interface that permits all elements except null. A PriorityQueue queue is ordered in PIPO
(priority-in, priority-out) order. This is achieved by natural order or a custom comparator to do the sorting and elements sorted first get the highest priority, in other words the ordering of the
elements represents their priority within the queue.
Often when discusiing Queues mention is made of the head and tail of the queue. The head of the Queue can be thought of as the least ordered element and the tail can be thought
of as the most ordered element. So for instance via natural order of A, B, C and D: A is the head and D is the tail.
PriorityQueue<E> Method OverviewTop
The table below shows the declarations of all the methods for the PriorityQueue<E> class implemented from the Queue<E> interface:
| Method Declaration | Description |
|---|---|
| Used in the example below | |
public boolean add(E o) | Adds the specified element to this PriorityQueue. |
public E poll() | Returns and removes the first element of this PriorityQueue. |
public boolean remove(Object o) | Removes a single instance of the specified element from this PriorityQueue if it is present. |
public int size() | Returns the number of elements in this PriorityQueue, ie. its cardinality. |
| Not used in the example below | |
public void clear() | Removes all of the elements from this PriorityQueue. |
public Comparator<? super E> comparator() | Returns the comparator used to order this PriorityQueue, or null if this PriorityQueue is sorted according to natural ordering (using Comparable). |
public Iterator<E> iterator() | Returns an iterator over the elements in this PriorityQueue. |
public boolean offer(E o) | Inserts the specified element into this PriorityQueue. |
public E peek() | Returns the first element of this PriorityQueue. |
Usage for the the first four methods is shown in the example below. For more information on the other methods in the PriorityQueue<E> class the following link will take you to the online version of
documentation for the JavaTM 2 Platform Standard Edition 5.0 API Specification. Take a look at the documentation for the PriorityQueue<E>
class which you can find by scrolling down the lower left pane and clicking on PriorityQueue.
PriorityQueue<E> ExampleTop
Lets write a simple class that creates an PriorityQueue and uses some of the methods from the PriorityQueue<E> class:
/*
Simple class to create an PriorityQueue and use several methods from the class
*/
import java.util.*; // Import the java.util package
public class PriorityQueueClass {
public static void main (String[] args) {
Queue<String> pq = new PriorityQueue<String>();
String s = "hhh";
pq.add(s);
pq.add("bbb");
pq.add("ccc");
pq.add("ddd");
pq.add("ggg");
pq.add("fff");
pq.add("aaa");
pq.add("eee");
System.out.println("priority queue size = " + pq.size());
System.out.println("priority queue contains: " + pq);
pq.poll();
pq.poll();
pq.remove(s);
System.out.println("priority queue size = " + pq.size());
System.out.println("priority queue contains: " + pq);
}
}
Save, compile and run the PriorityQueueClass class in directory c:\_Collections in the usual way.
The above screenshot shows the results of creating and running our PriorityQueueClass class and using several of the methods contained within the PriorityQueueClass<E> class.
Lesson 5 Complete
In this lesson we looked at Queues.
What's Next?
In our next lesson we look at the Map hierarchy, Map interface and four of its concrete implementations.
Homepage
Top