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

top1 top2

Figure4.21 Two stacks implemented within in a single array, both growing
toward the middle.

4.2.3 Comparison of Array-Based and Linked Stacks

All operations for the array-based and linked stack implementations take constant
time, so from a time efficiency perspective, neither has a significant advantage.
Another basis for comparison is the total space required. The analysis is similar to
that done for list implementations. The array-based stack must declare a fixed-size
array initially, and some of that space is wasted whenever the stack is not full. The
linked stack can shrink and grow but requires the overhead of a link field for every
element.
When multiple stacks are to be implemented, it is possible to take advantage of
the one-way growth of the array-based stack. This can be done by using a single
array to store two stacks. One stack grows inward from each end as illustrated by
Figure 4.21, hopefully leading to less wasted space. However, this only works well
when the space requirements of the two stacks are inversely correlated. In other
words, ideally when one stack grows, the other will shrink. This is particularly
effective when elements are taken from one stack and given to the other. If instead
both stacks grow at the same time, then the free space in the middle of the array
will be exhausted quickly.

4.2.4 Implementing Recursion

Perhaps the most common computer application that uses stacks is not even visible
to its users. This is the implementation of subroutine calls in most programming
language runtime environments. A subroutine call is normally implemented by
placing necessary information about the subroutine (including the return address,
parameters, and local variables) onto a stack. This information is called an ac-
tivation record. Further subroutine calls add to the stack. Each return from a
subroutine pops the top activation record off the stack. Figure 4.22 illustrates the
implementation of the recursive factorial function of Section 2.5 from the runtime
environment's point of view.
Consider what happens when we call fact with the value 4. We use to
indicate the address of the program instruction where the call to fact is made.
Thus, the stack must first store the address , and the value 4 is passed to fact .
Next, a recursive call to fact is made, this time with value 3. We will name the
program address from which the call is made 1 . The address 1 , along with the