Dynamic ArrayStack

Array implementation of Stack can be constructed by allocating an array of fixed-size, typically larger than the number of elements immediately required. Then, elements can be pushed/popped at the end of the array in constant time until this space is entirely consumed.

What should happen then?

  • Well, when the Stack is full, and a client invokes "push," we can throw an exception to signal there is no space left.

  • Alternatively, we can grow the underlying array. We can allocate a new underlying array and copy each element from the original array.

Consider the following implementation of push. Assume the array data has the capacity of 10 elements.

@Override
public void push(T value) {
  data[numElements++] = value;
  if (numElements == capacity) {
    grow();
  }
}

In the code above, numElement is the logical size of the array, whereas the capacity is its actual physical size.

Exercise Complete the implementation of the helper method grow. The new capacity must be double the old one.

private void grow() {
  // TODO: Implement me
}
Solution

In the following, we double the capacity each time growing the array.

private void grow() {
  capacity *= 2; 
  T[] tmp = (T[]) new Object[capacity];
  for (int i = 0; i < numElements; i++) {
    tmp[i] = data[i];
  }
  data = tmp;
}

Exercise What is the complexity of the grow() operation?

Solution

grow() runtime (and required auxiliary space) is $O(n)$ where $n$ is the number of the elements (stored in the Stack).

Aside: In the implementation of push, I have preemptively grew the array when increasing the capacity was not needed yet (not until the next push). However, it can be argued that a better approach is to grow the array reactivity when a push is requested, and the capacity is full.

Resources