The collections api - Data Structures and Problem Solving Using Java - page 261

figure 6.27
The queue model:
Input is by enqueue ,
output is by getFront ,
and deletion is by
dequeue.

enqueue dequ eue

Queue

getFront

system, for example, when jobs are submitted to a printer, we expect the least
recent or most senior job to be printed first. This order is not only fair but it is
also required to guarantee that the first job does not wait forever. Thus you can
expect to find printer queues on all large systems.
The basic operations supported by queues are the following:

enqueue , or insertion at the back of the line

n

dequeue , or removal of the item from the front of the line

n

getFront , or access of the item at the front of the line

n

Figure 6.27 illustrates these queue operations. Historically, dequeue and
getFront have been combined into one operation; we do this by having dequeue
return a reference to the item that it has removed.
Because the queue operations and the stack operations are restricted simi-
larly, we expect that they should also take a constant amount of time per
query. This is indeed the case. All of the basic queue operations take
time. We will see several applications of queues in the case studies.

Queue operations
take a constant
amount of time.

O ( )

6.6.4 stacks and queues in the collections api

The Collections API provides a Stack class but no queue class. The Stack
methods are push , pop , and peek . However, the Stack class extends Vector and
is slower than it needs to be; like Vector , its use is no longer in vogue and can
be replaced with List operations. Before Java 1.4, the only java.util support
for queue operations was to use a LinkedList (e.g., addLast , removeFirst , and
getFirst ). Java 5 adds a Queue interface, part of which is shown in Figure 6.28.
However, we still must use LinkedList methods. The new methods are add ,
remove , and element .

The Collections
API provides a
Stack class but no
queue class. Java
5 adds a Queue
interface.

sets

6.7

A Set is a container that contains no duplicates. It supports all of the Collection
methods. Most importantly, recall that as we discussed in Section 6.5.3, contains
for a List is inefficient, regardless of whether the List is an ArrayList or a

A Set contains no
duplicates.