6.5 Stacks implemented using arrays

The array-based stack contains a pre-allocated internal array, and the size of the stack.

datatype ArrayStack implements Stack:
    internalArray = new Array(1000)  // Internal array containing the stack elements
    size = 0                         // Size of stack, also index of the next free slot

Note that here we use an internal capacity of 1000 for the internal array, but we could use any positive value.

Where should the top of the stack be?

The only important design decision to be made is which end of the array should represent the top of the stack. It might be tempting to let the top be the first element in the array, i.e., the element at position 0. However, this is inefficient, because then we have to shift all elements in the array one position to the left or to the right, whenever we want to push to or pop from the stack.

Much better is to have the top be the last element, i.e. the element at position n−1n-1 (if nn is the number of elements). Then we don’t have to shift around a lot of element, but instead just move the pointer to the left or the right.

Pushing to the stack

The size variable refers to the last uninhabited cell in the array. So, to push an element onto the stack, we assign internalArray[size] and then increase the size.

datatype ArrayStack:
    ...
    push(elem):
        internalArray[size] = elem
        size = size + 1

Array stack – push exercise.

Popping from the stack

To pop an element from the stack we do the reverse of pushing: first we decrease the size, then we remember the result in a temporary variable. After that we can clear the old top cell in the array and return the result.

datatype ArrayStack:
    ...
    pop():
        size = size - 1
        result = internalArray[size]
        internalArray[size] = null  // For garbage collection
        return result

Array stack – pop exercise.

Example: Implementing two stacks using one array

If you need to use two stacks at the same time, you can take advantage of the one-way growth of the array-based stack by using a single array to store two stacks. One stack grows inward from each end, 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.