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

/ ** StackADT * /
publicinterfaceStack<E>{

/ ** Reinitializethestack.Theuserisresponsiblefor
reclaimingthestorageusedbythestackelements. * /
publicvoidclear();

/ ** Pushanelementontothetopofthestack.
@paramitTheelementbeingpushedontothestack. * /
publicvoidpush(Eit);

/ ** Removeandreturntheelementatthetopofthestack.
@returnTheelementatthetopofthestack. * /
publicEpop();

/ ** @returnAcopyofthetopelement. * /
publicEtopValue();

/ ** @returnThenumberofelementsinthestack. * /
publicintlength();

};

Figure4.18 The stack ADT.

The array-based stack implementation is essentially a simplified version of the
array-based list. The only important design decision to be made is which end of
the array should represent the top of the stack. One choice is to make the top be
at position 0 in the array. In terms of list functions, all insert and remove
operations would then be on the element in position 0. This implementation is
inefficient, because now every push or pop operation will require that all elements
currently in the stack be shifted one position in the array, for a cost of (n) if there
are n elements. The other choice is have the top element be at position n1 when
there are n elements in the stack. In other words, as elements are pushed onto
the stack, they are appended to the tail of the list. Method pop removes the tail
element. In this case, the cost for each push or pop operation is only (1).
For the implementation of Figure 4.19, top is defined to be the array index of
the first free position in the stack. Thus, an empty stack has top set to 0, the first
available free position in the array. (Alternatively, top could have been defined to
be the index for the top element in the stack, rather than the first free position. If
this had been done, the empty list would initialize top as 1.) Methods push and
pop simply place an element into, or remove an element from, the array position
indicated by top . Because top is assumed to be at the first free position, push
first inserts its value into the top position and then increments top , while pop first
decrements top and then removes the top element.