Java Reference
In-Depth Information
Self-Test Exercises
15. What operations are easier to implement with a doubly linked list compared
with a singly linked list? What operations are more diffi cult?
16. If the
addToStart
method from Display 15.25 were removed, how could we
still add a new node to the head of the list?
The Stack Data Structure
A
stack
is not necessarily a linked data structure, but it can be implemented as a
linked list. A stack is a data structure that removes items in the reverse of the order in
which they were inserted. So if you insert “
one
”, then “
two
”, and then “
three
” into
a stack and then remove them, they will come out in the order “
three
”, then “
two
”,
and finally “
one
”. Stacks are discussed in more detail in Chapter 11 . A linked list that
inserts and deletes only at the head of the list (such as those in Displays 15.3 or 15.8)
is, in fact, a stack.
You can imagine the stack data structure like a stack of trays in a cafeteria. You can
push
a new tray on top of the stack to make a taller stack. Alternately, you can
pop
the topmost tray off the stack until there are no more trays to remove. A definition of a
Stack
class is shown in Display 15.27 that is based on the linked list from Display 15.3.
A short demonstration program is shown in Display 15.28. The
addToStart
method
has been renamed to
push
to use stack terminology. Similarly, the
deleteHeadNode
method has been renamed to
pop
and returns the
String
from the top of the stack.
Although not shown here to keep the definition simple, it would be appropriate to add
other methods such as
peek
,
clone
, or
equals
or to convert the class to use a generic
data type.
stack
push and pop
Stacks
A
stack
is a last-in/first-out data structure; that is, the data items are retrieved in the
opposite order to which they were placed in the stack.
Display 15.27
A
Stack
Class
(part 1 of 2)
1
import
java.util.NoSuchElementException;
2
public class
Stack
3 {
4
private class
Node
5 {
6
private
String item;
7
private
Node link;
(continued)
