Lists, Stacks, and Queues - Data Structures and Algorithm Analysis - page 120

/ ** Linkedstackimplementation * /
classLStack<E>implementsStack<E>{
privateLink<E>top; //Pointertofirstelement
privateintsize; //Numberofelements

/ ** Constructors * /
publicLStack(){top=null;size=0;}
publicLStack(intsize){top=null;size=0;}

/ ** Reinitializestack * /
publicvoidclear(){top=null;size=0;}

/ ** Put"it"onstack * /
publicvoidpush(Eit){
top=newLink<E>(it,top);
size++;

}

/ ** Remove"it"fromstack * /
publicEpop(){
asserttop!=null:"Stackisempty";
Eit=top.element();
top=top.next();
size--;
returnit;

}

/ ** @returnTopvalue * /
publicEtopValue(){
asserttop!=null:"Stackisempty";
returntop.element();

}

/ ** @returnStacklength * /
publicintlength(){returnsize;}

Figure4.20 Linked stack class implementation.

4.2.2 Linked Stacks

The linked stack implementation is quite simple. The freelist of Section 4.1.2 is
an example of a linked stack. Elements are inserted and removed only from the
head of the list. A header node is not used because no special-case code is required
for lists of zero or one elements. Figure 4.20 shows the complete linked stack
implementation. The only data member is top , a pointer to the first (top) link node
of the stack. Method push first modifies the next field of the newly created link
node to point to the top of the stack and then sets top to point to the new link
node. Method pop is also quite simple. Variable temp stores the top nodes' value,
while ltemp links to the top node as it is removed from the stack. The stack is
updated by setting top to point to the next link in the stack. The old top node is
then returned to free store (or the freelist), and the element value is returned.