Queues, Deques, and Priority Queues - Data Structures and Abstractions with Java - page 261

The following two constructors are defined by this class:
public ArrayDeque()
Creates an empty deque whose initial capacity is 16 entries.
public ArrayDeque( int initialCapacity)
Creates an empty deque having a given initial capacity.
Instances of ArrayDeque grow in size as needed by a client.

Note: If you want to use a standard class instead of your own to create a stack, you should
use an instance of the standard class ArrayDeque , but not the standard class Stack . Stack is
now considered a legacy class. That is, it is retained in the Java Class Library only to support
previously written Java programs.

The ADT Priority Queue

10.19

Although a bank serves its customers in the order in which they arrive, an emergency room treats
patients according to the urgency of their malady. The bank organizes its customers into chronolog-
ical order by using a queue. A hospital assigns a priority to each patient that overrides the time at
which the patient arrived.

The ADT priority queue organizes objects according to their priorities. Exactly what form a prior-
ity takes depends on the nature of the object. Priorities can be integers, for example. A priority of 1 can be
the highest priority, or it can be the lowest. By making the objects Comparable , we can hide this detail in
the objects' method compareTo . The priority queue then can use compareTo to compare objects by their
priorities. Thus, the priority queue can have the Java interface given in Listing 10-5. We use the notation
? super T , which Segment 8.2 of Chapter 8 introduced, to mean any super class of the generic type T .

VideoNote

The ADTs deque and
priority queue

LISTING 10-5

An interface for the ADT priority queue

public interface PriorityQueueInterface<T extends Comparable<? super T>>
{

/** Adds a new entry to this priority queue.
@param newEntry an object */
public void add(T newEntry);

/** Removes and returns the item with the highest priority.
@return either the object with the highest priority or, if the
priority queue is empty before the operation, null */
public T remove();

/** Retrieves the item with the highest priority.
@return either the object with the highest priority or, if the
priority queue is empty, null */
public T peek();

/** Detects whether this priority queue is empty.
@return true if the priority queue is empty, or false otherwise */
public boolean isEmpty();