Java Reference
In-Depth Information
• Stacks are used by compilers to evaluate arithmetic expressions and generate machine-language
code to process the expressions.
• The technique of implementing each stack method as a call to a
List
method is called delega-
tion—the stack method invoked delegates (p. 890) the call to the appropriate
List
method.
Section 21.6 Queues
• A queue (p. 890) is similar to a checkout line in a supermarket—the first person in line is serviced
first, and other customers enter the line only at the end and wait to be serviced.
• Queue nodes are removed only from the head (p. 890) of the queue and are inserted only at the
tail. For this reason, a queue is referred to as a first-in, first-out FIFOaaaa data structure.
• The insert and remove operations for a queue are known as
enqueue
(p. 891) and
dequeue
(p. 891).
• Queues have many uses in computer systems. Most computers have only a single processor, so
only one application at a time can be serviced. Entries for the other applications are placed in a
queue. The entry at the front of the queue is the next to receive service. Each entry gradually ad-
vances to the front of the queue as applications receive service.
Section 21.7 Trees
• A tree is a nonlinear, two-dimensional data structure. Tree nodes contain two or more links.
• A binary tree (p. 893) is a tree whose nodes all contain two links. The root node (p. 893) is the
first node in a tree.
• Each link in the root node refers to a child (p. 893). The left child (p. 893) is the first node in
the left subtree (p. 893), and the right child (p. 893) is the first node in the right subtree (p. 893).
• The children of a node are called siblings (p. 893). A node with no children is a leaf node (p. 893).
• In a binary search tree (p. 894) with no duplicate values, the values in any left subtree are less than
the value in the subtree's parent node, and the values in any right subtree are greater than the value
in the subtree's parent node. A node can be inserted only as a leaf node in a binary search tree.
• An inorder traversal (p. 894) of a binary search tree processes the node values in ascending order.
• In a preorder traversal (p. 894), the value in each node is processed as the node is visited. Then
the values in the left subtree are processed, then the values in the right subtree.
• In a postorder traversal (p. 894), the value in each node is processed after the values of its children.
• The binary search tree facilitates duplicate elimination (p. 899). As the tree is created, attempts to
insert a duplicate value are recognized, because a duplicate follows the same “go left” or “go right”
decisions on each comparison as the original value did. Thus, the duplicate eventually is compared
with a node containing the same value. The duplicate value can be discarded at this point.
• In a tightly packed tree (p. 900), each level contains about twice as many elements as the previous
one. So a tightly packed binary search tree with
n
elements has log
2
n
levels, and thus at most log
2
n
comparisons would have to be made either to find a match or to determine that no match ex-
ists. Searching a (tightly packed) 1000-element binary search tree requires at most 10 compari-
sons, because 2
10
> 1000. Searching a (tightly packed) 1,000,000-element binary search tree
requires at most 20 comparisons, because 2
20
> 1,000,000.
Self-Review Exercises
21.1
Fill in the blanks in each of the following statements:
a)
A self- class is used to form dynamic data structures that can grow and shrink
at execution time.
