Java Reference
In-Depth Information
6.19
Removing the top.
We can remove the stack's top entry by using
Vector
's method
remove
. The
argument to this method is the index of the last entry in the vector, since that entry is at the top of
the stack. This index is 1 less than the vector's current size
stack.size()
.
public
T pop()
{
T top =
null
;
if
(!isEmpty())
top = stack.remove(stack.size() - 1);
return
top;
}
// end pop
6.20
The rest of the class.
The remaining public methods
isEmpty
and
clear
invoke analogous
Vector
methods:
public
boolean
isEmpty()
{
return
stack.isEmpty();
}
// end isEmpty
public void
clear()
{
stack.clear();
}
// end clear
Question 9
If a vector contains the entries in a stack, is it reasonable to maintain the
stack's top entry in the vector's first element?
Design Decision:
Should
VectorStack
extend
Vector
?
The previous implementation of
VectorStack
contains an instance of
Vector
. Suppose that we
instead used inheritance to derive
VectorStack
from
Vector
. The resulting class would have all the
methods of
Vector
in addition to those in
StackInterface
. However, these
Vector
methods would
allow a client to add or remove entries anywhere within the stack, thus violating the premise of the
ADT stack. Instead of a stack, we would have an enhanced vector. But a stack is not a vector. Since
we do not have an
is-a
relationship between stacks and vectors, we should not use inheritance to
define
VectorStack
.
The class
java.util.Stack
in the Java Class Library that we introduced in Segment 5.23 of
the previous chapter does extend
Vector
. Thus, an instance of
Stack
is not really a stack.
C
HAPTER
S
UMMARY
You can implement a stack by using a chain of linked nodes that has only a head reference. The stack opera-
tions execute fastest if the first node in the chain references the stack's top entry. This is true because you
can add, remove, or access a chain's first node faster than any other node.
●
The stack operations are O(1) for a linked implementation.
●
You can implement a stack by using an array. If the first location in the array contains the stack's bottom
entry, no array elements will be moved when you add or remove stack entries.
●
Resizing an array avoids a stack that is too full to accept another entry. However, the array generally contains
locations that are unused.
●
