Java Reference
In-Depth Information
structure. The link member in the bottom node is set to
null
to indicate the bottom of
the stack. A stack is not required to be implemented as a linked list—it can also be imple-
mented using an array.
The primary methods for manipulating a stack are
push
and
pop
, which add a new
node to the top of the stack and remove a node from the top of the stack, respectively.
Method
pop
also returns the data from the popped node.
Stacks have many interesting applications. For example, when a program calls a
method, the called method must know how to return to its caller, so the return address of
the calling method is pushed onto the program-execution stack (discussed in Section 6.6).
If a series of method calls occurs, the successive return addresses are pushed onto the stack
in last-in, first-out order so that each method can return to its caller. Stacks support recur-
sive method calls in the
same
manner as they do conventional nonrecursive method calls.
The program-execution stack also contains the memory for local variables on each
invocation of a method during a program's execution. When the method returns to its
caller, the memory for that method's local variables is popped off the stack, and those vari-
ables are no longer known to the program. If the local variable is a reference and the object
to which it referred has no other variables referring to it, the object can be garbage col-
lected.
Compilers use stacks to evaluate arithmetic expressions and generate machine-lan-
guage code to process them. The exercises in this chapter explore several applications of
stacks, including using them to develop a complete working compiler. Also, package
java.util
contains class
Stack
(see Chapter 16) for implementing and manipulating
stacks that can grow and shrink during program execution.
In this section, we take advantage of the close relationship between lists and stacks to
implement a stack class by reusing the
List<T>
class of Fig. 21.3. We demonstrate two dif-
ferent forms of reusability. First, we implement the stack class by extending class
List
.
Then we implement an identically performing stack class through
composition
by
including a reference to a
List
object as a
private
instance variable. The list, stack and
queue data structures in this chapter are implemented to store references to objects of any
type to encourage further reusability.
Stack Class That Inherits from
List<T>
Figures 21.10 and 21.11 create and manipulate a stack class that extends the
List<T>
class
of Fig. 21.3. We want the stack to have methods
push
,
pop
,
isEmpty
and
print
. Essential-
ly, these are the
List<T>
methods
insertAtFront
,
removeFromFront
,
isEmpty
and
print
.
Of course, class
List<T>
contains other methods (such as
insertAtBack
and
removeFrom-
Back
) that we would rather not make accessible through the
public
interface to the stack
class. It's important to remember that all methods in
List<T>
's
public
interface class also
are
public
methods of the subclass
StackInheritance<T>
(Fig. 21.10). Each method of
StackInheritance<T>
calls the appropriate
List<T>
method—for example, method
push
calls
insertAtFront
and method
pop
calls
removeFromFront
.
StackInheritance<T>
cli-
ents can call methods
isEmpty
and
print
because they're inherited from
List<T>
. Class
StackInheritance<T>
is declared in package
com.deitel.datastructures
(line 3) for re-
use.
StackInheritance<T>
does not import
List<T>
—the classes are in the same package.
Class
StackInheritanceTest
's method
main
(Fig. 21.11) creates an object of class
StackInheritance<T>
called
stack
(line 10). The program pushes integers onto the stack
(lines 13, 15, 17 and 19).
Autoboxing
is used here to insert
Integer
objects into the data
