Stack Implementations - Data Structures and Abstractions with Java - page 138

reference, we can add, remove, or access its first node faster than any other node. Thus, the
stack operations will execute fastest if the first node in the chain references the top entry in
the stack, as Figure 6-1 illustrates.

Also note in the figure that each node in the chain references one entry in the stack. Nodes are
allocated—that is, created—only when needed for a new entry. They are deallocated when an entry
is removed. Recall from the note in Segment 3.24 of Chapter 3 that the Java run-time environment
automatically reclaims, or deallocates, memory that a program no longer references, without
explicit instruction from the programmer.

VideoNote

The Class LinkedStack

FIGURE 6-1

A chain of linked nodes that implements a stack

Chain

topNode

Top entry of stack

Stack

Note: If you use a chain of linked nodes to implement a stack, the first node should refer-
ence the stack's top entry.

6.2

An outline of the class. The linked implementation of the stack has a data field topNode , which is
the head reference of the chain of nodes. The default constructor sets this field to null . An outline
of our class appears in Listing 6-1.
Each node in the chain is an instance of the private class Node that is defined within the class
LinkedStack . This class has set and get methods and is like the one you saw in Listing 3-4 of Chapter 3.

LISTING 6-1

An outline of a linked implementation of the ADT stack

/**

A class of stacks whose entries are stored in a chain of nodes.
@author Frank M. Carrano

*/
public class LinkedStack<T> implements StackInterface<T>
{

private Node topNode; // references the first node in the chain

public LinkedStack()
{

topNode = null ;
} // end default constructor