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

< Implementations of the stack operations go here. >
. . .

private class Node
{

private T data; // entry in stack
private Node next; // link to next node

< Constructors and the methods getData , setData , getNextNode , and setNextNode
are here. >
} // end Node
} // end LinkedStack

6.3

Adding to the top. We push an entry onto the stack by first allocating a new node that references
the stack's existing chain, as Figure 6-2a illustrates. This reference is in topNode , the head refer-
ence to the chain. We then set topNode to reference the new node, as in Figure 6-2b. Thus, the
method push has the following definition:
public void push(T newEntry)
{

Node newNode = new Node(newEntry, topNode);
topNode = newNode;
} // end push
This operation is independent of the other entries in the stack. Its performance is thus O(1).

FIGURE 6-2

(a) A new node that references the node at the top of the stack;
(b) the new node is now at the top of the stack

(a)

newNode

topNode

(b)

topNode

6.4

Retrieving the top. We get the top entry in the stack by accessing the data portion of the first node in
the chain. Thus, peek , like push , is an O(1) operation. Note that if the stack is empty, peek returns null .
public T peek()
{

T top = null ;