chap listsstacksand queues top top figure two stacks implemented within in single arrayboth growing toward the middle is then returned to free store (or the freelist)and the element value is returned as the value of the pop method comparison of array-based and linked stacks all operations for the array-based and linked stack implementations take constant timeso from time efficiency perspectiveneither has 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 fixed-size array initiallyand some of that space is wasted whenever the stack is not full the linked stack can shrink and grow but requires the overhead of link field for every element when multiple stacks are to be implementedit is possible to take advantage of the one-way growth of the array-based stack this can be done by using single array to store two stacks one stack grows inward from each end as illustrated by figure hopefully leading to less wasted space howeverthis only works well when the space requirements of the two stacks are inversely correlated in other wordsideally when one stack growsthe 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 timethen the free space in the middle of the array will be exhausted quickly 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 subroutine call is normally implemented by placing necessary information about the subroutine (including the return addressparametersand local variablesonto stack this information is called an activation record further subroutine calls add to the stack each return from subroutine pops the top activation record off the stack figure illustrates the implementation of the recursive factorial function of section from the runtime environment' point of view