Java Reference
In-Depth Information
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/
.
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.