Java Reference
In-Depth Information
{
return list.size();
}
private LinkedList list;
}
You would definitely not want to use an
ArrayList
to implement a queue.
Removing the first element of an array list is inefficientȌall other elements must be
moved towards the beginning. However, Exercise P15.12 shows you how to
implement a queue efficiently as a Ȓcircularȓ array, in which all elements stay at the
position at which they were inserted, but the index values that denote the head and tail
of the queue change when elements are added and removed.
In this chapter, you have seen the two most fundamental abstract data types, arrays
and lists, and their concrete implementations. You also learned about the stack and
queue types. In the next chapter, you will see additional data types that require more
sophisticated implementation techniques.
688
689
S
ELF
C
HECK
9.
Draw a sketch of the abstract queue type, similar to
Figures 9
and
11
.
10.
Why wouldn't you want to use a stack to manage print jobs?
R
ANDOM
F
ACT
15.1: Standardization
You encounter the benefits of standardization every day. When you buy a light
bulb, you can be assured that it fits the socket without having to measure the
socket at home and the light bulb in the store. In fact, you may have experienced
how painful the lack of standards can be if you have ever purchased a flashlight
with nonstandard bulbs. Replacement bulbs for such a flashlight can be difficult
and expensive to obtain.
Programmers have a similar desire for standardization. Consider the important
goal of platform independence for Java programs. After you compile a Java
program into class files, you can execute the class files on any computer that has a
Java virtual machine. For this to work, the behavior of the virtual machine has to
be strictly defined. If virtual machines don't all behave exactly the same way, then
the slogan of Ȓwrite once, run anywhereȓ turns into Ȓwrite once, debug
