LISTS, STACKS, QUEUES, AND PRIORITY QUEUES - Introduction to Java Programming: Comprehensive Version - page 783

20.9 Queues and Priority Queues
In a priority queue, the element with the highest priority is removed first.

Key
Point

A queue is a first-in, first-out data structure. Elements are appended to the end of the queue
and are removed from the beginning of the queue. In a priority queue , elements are assigned
priorities. When accessing elements, the element with the highest priority is removed first.
This section introduces queues and priority queues in the Java API.

queue
priority queue

20.9.1 The Queue Interface
The Queue interface extends java.util.Collection with additional insertion, extraction,
and inspection operations, as shown in Figure 20.12.

Queue interface

«interface»
java.util.Collection<E>

«interface»
java.util.Queue<E>

+ offer(element: E): boolean
+ poll(): E

Inserts an element into the queue.
Retrieves and removes the head of this queue, or null
if this queue is empty.
Retrieves and removes the head of this queue and
throws an exception if this queue is empty.
Retrieves, but does not remove, the head of this queue,
returning null if this queue is empty.
Retrieves, but does not remove, the head of this queue,
throws an exception if this queue is empty.

+ remove(): E

+ peek(): E

+ element(): E

F IGURE 20.12

The Queue interface extends Collection to provide additional insertion,
extraction, and inspection operations.

The offer method is used to add an element to the queue. This method is similar to the
add method in the Collection interface, but the offer method is preferred for queues.
The poll and remove methods are similar, except that poll() returns null if the queue is
empty, whereas remove() throws an exception. The peek and element methods are simi-
lar, except that peek() returns null if the queue is empty, whereas element() throws an
exception.

queue operations

20.9.2 Deque and LinkedList
The LinkedList class implements the Deque interface, which extends the Queue inter-
face, as shown in Figure 20.13. Therefore, you can use LinkedList to create a queue.
LinkedList is ideal for queue operations because it is efficient for inserting and removing
elements from both ends of a list.
Deque supports element insertion and removal at both ends. The name deque is short for
“double-ended queue” and is usually pronounced “deck.” The Deque interface extends Queue
with additional methods for inserting and removing elements from both ends of the queue. The
methods addFirst(e) , removeFirst() , addLast(e) , removeLast() , getFirst() ,
and getLast() are defined in the Deque interface.