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 difficult?
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 the one in Display 15.3 or in Display 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;
