Stacks and queues - Data Structures and Problem Solving Using Java - page 596

is, in effect, the same as push . However, because we are interested in a general dis-
cussion of the algorithms, we implement the array-based stack using basic arrays,
duplicating some of the code seen earlier in the ArrayList implementations.

16.1.1 stacks

As Figure 16.1 shows, a stack can be implemented with an array and an inte-
ger. The integer tos ( top of stack ) provides the array index of the top element
of the stack. Thus when tos is -1, the stack is empty. To push , we increment
tos and place the new element in the array position tos . Accessing the top
element is thus trivial, and we can perform the pop by decrementing tos . In
Figure 16.1, we begin with an empty stack. Then we show the stack after
three operations: push(a) , push(b) , and pop .
Figure 16.2 shows the skeleton for the array-based Stack class. It specifies
two data members: theArray , which is expanded as needed, stores the items in
the stack; and topOfStack gives the index of the current top of the stack. For an
empty stack, this index is -1. The constructor is shown in Figure 16.3.

A stack can be
implemented with
an array and an
integer that indi-
cates the index of
the top element.

The public methods are listed in lines 22-33 of the skeleton. Most of
these routines have simple implementations. The isEmpty and makeEmpty rou-
tines are one-liners, as shown in Figure 16.4. The push method is shown in
Figure 16.5. If it were not for the array doubling, the push routine would be
only the single line of code shown at line 9. Recall that the use of the prefix
++ operator means that topOfStack is incremented and that its new value is
used to index theArray . The remaining routines are equally short, as shown in
Figures 16.6 and 16.7. The postfix -- operator used in Figure 16.7 indicates
that, although topOfStack is decremented, its prior value is used to index
theArray .
If there is no array doubling, every operation takes constant time. A push
that involves array doubling will take O ( N ) time. If this were a frequent
occurrence, we would need to worry. However, it is infrequent because an

Most of the stack
routines are appli-
cations of previ-
ously discussed
ideas.

Recall that array
doubling does not
affect performance
in the long run.

figure 16.1
How the stack
routines work:
(a) empty stack;
(b) push(a) ;
(c) push(b) ;
(d) pop( )

b tos (1)

a tos (0) a a tos (0)

tos (-1)

(a) (b) (c) (d)