Java Reference
In-Depth Information
a queue is a
first-in, first-out
(
FIFO
) data structure. The insert and remove operations are
known as
enqueue
and
dequeue
.
Queues have many uses in computer systems. Each CPU in a computer can service
only one application at a time. Each application requiring processor time is placed in a
queue. The application at the front of the queue is the next to receive service. Each appli-
cation gradually advances to the front as the applications before it receive service.
Queues are also used to support
print spooling
. For example, a single printer might
be shared by all users of a network. Many users can send print jobs to the printer, even
when the printer is already busy. These print jobs are placed in a queue until the printer
becomes available. A program called a
spooler
manages the queue to ensure that, as each
print job completes, the next one is sent to the printer.
Information packets also
wait
in queues in computer networks. Each time a packet
arrives at a network node, it must be routed to the next node along the path to the packet's
final destination. The routing node routes one packet at a time, so additional packets are
enqueued until the router can route them.
A file server in a computer network handles file-access requests from many clients
throughout the network. Servers have a limited capacity to service requests from clients.
When that capacity is exceeded, client requests
wait
in queues.
Figure 21.13 creates a
Queue<T>
class that contains a
List<T>
(Fig. 21.3) object and
provides methods
enqueue
,
dequeue
,
isEmpty
and
print
. Class
List<T>
contains some
methods (e.g.,
insertAtFront
and
removeFromBack
) that we'd rather not make accessible
through
Queue<T>
's
public
interface. Using composition enables us to hide class
List<T>
's other
public
methods from clients of class
Queue<T>
. Each
Queue<T>
method
calls an appropriate
List<T>
method—method
enqueue
calls
List<T>
method
insertAt-
Back
, method
dequeue
calls
List<T>
method
removeFromFront
, method
isEmpty
calls
List<T>
method
isEmpty
and method
print
calls
List<T>
method
print
. For reuse, class
Queue<T>
is declared in package
com.deitel.datastructures
.
1
// Fig. 21.13: Queue.java
2
// Queue uses class List.
3
package
com.deitel.datastructures;
4
5
public class
Queue
6
{
7
private
List<T> queueList;
8
9
// constructor
10
public
Queue()
11
{
12
queueList =
new
List<T>(
"queue"
);
13
}
14
15
// add object to queue
16
public void
enqueue(T object)
17
{
18
queueList.insertAtBack(object);
19
}
Fig. 21.13
|
Queue
uses class
List
. (Part 1 of 2.)