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

Retrieves the entry at the front of this queue, but throws NoSuchElementException if the queue
is empty.

public T peek()

Retrieves the entry at the front of this queue, but returns null if the queue is empty.

public boolean isEmpty()
Detects whether this queue is empty.

public void clear()
Removes all entries from this queue.

public int size()

Gets the number of elements currently in this queue.

Some of these methods occur in pairs. Both add and offer add a new entry to the queue. If the opera-
tion is unsuccessful, add throws an exception but offer returns false. Likewise, each of the methods
remove and poll removes and returns the entry at the front of the queue. If the queue is empty before the
operation, remove throws an exception but poll returns null . Finally, peek and element each retrieve the
entry at the front of the queue. If the queue is empty, element throws an exception but peek returns null .
You can learn more about Queue and the other components of the Java Class Library at
download.oracle.com/javase/7/docs/api/ .

The ADT Deque

10.14

Imagine that you are in a line at the post office. When it is finally your turn, the postal agent asks
you to fill out a form. You step aside to do so and let the agent serve the next person in the line.
After you complete the form, the agent will serve you next. Essentially, you go to the front of the
line, rather than waiting in line twice.
Similarly, suppose that you join a line at its end but then immediately decide it is too long, so you
leave it. To simulate both of these examples, you want an ADT whose operations enable you to add,
remove, or retrieve entries at both the front and back of a queue. Such an ADT is called a double-
ended queue , or deque (pronounced “deck”).
A deque has both queuelike operations and stacklike operations. For example, the deque opera-
tions addToBack and removeFront resemble the queue operations enqueue and dequeue , respec-
tively. And addToFront and removeFront are like the stack operations push and pop , respectively. In
addition, a deque has the operations getFront , getBack , and removeBack . Figure 10-10 illustrates a
deque and these methods.

Note: Although the ADT deque is called a double-ended queue, it actually behaves like a double-
ended stack. As Figure 10-10 shows, you can push, pop, or get items at either of its ends.

FIGURE 10-10

An instance d of a deque

The deque d

d.addToBack(item)
d.removeBack()
d.getBack()

d.addToFront(item)
d.removeFront()
d.getFront()

Front

Back

Since the specifications for the deque operations are like those you have already seen for a
queue and a stack, we provide the brief Java interface in Listing 10-4 without comments.