Implement a Stack Using an Array in Java

In the previous part, we wrote a stack as an adapter around an ArrayDeque. In this part of the tutorial, I’ll show you how to implement a stack – without any Java Collections classes – using an array.

The principle is simple: We create an empty array and fill it from left to right (i.e., ascending from index 0) with the elements placed on the stack. To remove the elements, we read them from right to left (and remove them from the array).

The following diagram shows a stack with an array named elements that can hold eight elements. So far, four elements have been placed on the stack.

The number of elements (not the size of the array) is stored in the numberOfElements variable. The value of this variable tells us at which position in the array we have to insert or read an element:

• Insert: at position numberOfElements
• Read: at position numberOfElements - 1

Source Code for a Stack with a Fixed Size Array

As long as we don’t need to resize the array, the implementation is simple, as the following Java code shows (BoundedArrayStack class on GitHub):

public class BoundedArrayStack<E> implements Stack<E> {

  private final Object[] elements;

  private int numberOfElements;

  public BoundedArrayStack(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }

  @Override
  public void push(E item) {
    if (numberOfElements == elements.length) {
      throw new IllegalStateException("The stack is full");
    }
    elements[numberOfElements] = item;
    numberOfElements++;
  }

  @Override
  public E pop() {
    E element = elementAtTop();
    elements[numberOfElements - 1] = null;
    numberOfElements--;
    return element;
  }

  @Override
  public E peek() {
    return elementAtTop();
  }

  private E elementAtTop() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }

    @SuppressWarnings("unchecked")
    E element = (E) elements[numberOfElements - 1];

    return element;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}

pop() sets the vacated slot to null. Without this line, the array would keep a reference to the removed element – and the garbage collector could not free it as long as the stack is in use and no later push() overwrites the slot.

It gets a bit more complicated when more elements are to be pushed onto the stack than the array can hold. An array cannot grow. I will show you how to do it anyway in the next chapter.

Implementing a Stack with a Variable Size Array

When the array is full, we must:

1. create a new, larger array,
2. copy the elements from the original array into the new array, and
3. finally, discard the old array.

The following diagram shows these three steps for a full array of six elements that is doubled to twelve slots:

In Java, a single call to Arrays.copyOf() takes care of the first two steps: We pass the method the old array and the desired size of the new one. The garbage collector takes care of the third step as soon as elements points to the new array.

Source Code for the Stack with a Variable Size Array

The following code shows a stack initially created with an array for ten elements. Like BoundedArrayStack, the constructor rejects an initial capacity below 1: For an empty array, calculateNewCapacity() would calculate a capacity of 0 again – the array could never grow.

Each time the push() method is called, it checks whether the array is full. If it is, the grow() method is called.

The grow() method, in turn, calls calculateNewCapacity() to calculate the new size of the array. As long as the array holds fewer than 64 elements, we double it; after that, we grow it by a factor of 1.5 – similar to ArrayDeque. Starting with ten elements, the array thus grows to 20, 40, 80, 120, 180 slots, and so on.

Growing the array by a factor rather than by a fixed number of slots has a reason: Each copy costs O(n), but it happens less often the larger the array gets. Spread over all calls, push() thus takes amortized constant time, i.e., O(1). If the array grew by, say, ten slots at a time instead, it would have to be copied every ten calls – that would be O(n) per push().

The code also specifies a maximum size for the array: Integer.MAX_VALUE - 8. This is the same value the JDK uses as ArraysSupport.SOFT_MAX_ARRAY_LENGTH, because HotSpot rejects arrays with a length close to Integer.MAX_VALUE with an OutOfMemoryError – even if there is enough free heap. Once the maximum size is reached and another element is pushed, calculateNewCapacity() throws an IllegalStateException (unless we got an OutOfMemoryError before).

Here is the code (class ArrayStack on GitHub):

public class ArrayStack<E> implements Stack<E> {

  public static final int MAX_SIZE = Integer.MAX_VALUE - 8;
  private static final int DEFAULT_INITIAL_CAPACITY = 10;
  private Object[] elements;
  private int numberOfElements;

  public ArrayStack() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  public ArrayStack(int initialCapacity) {
    if (initialCapacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[initialCapacity];
  }

  @Override
  public void push(E item) {
    if (elements.length == numberOfElements) {
      grow();
    }
    elements[numberOfElements] = item;
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = calculateNewCapacity(elements.length);
    elements = Arrays.copyOf(elements, newCapacity);
  }

  static int calculateNewCapacity(int currentCapacity) {
    if (currentCapacity == MAX_SIZE) {
      throw new IllegalStateException("Can't grow further");
    }

    int newCapacity = currentCapacity + calculateIncrement(currentCapacity);

    if (newCapacity > MAX_SIZE || newCapacity < 0 /* overflow */) {
      newCapacity = MAX_SIZE;
    }

    return newCapacity;
  }

  private static int calculateIncrement(int currentCapacity) {
    return currentCapacity < 64 ? currentCapacity : currentCapacity / 2;
  }

  // pop(), peek(), elementAtTop(), isEmpty() are the same as in BoundedArrayStack

}

The methods pop(), peek(), elementAtTop(), and isEmpty() are identical to those in the BoundedArrayStack presented above, so I have not printed them again.

The ArrayStack in the form printed above cannot yet shrink the array again (we don’t want to waste too much memory). Feel free to try to extend the implementation yourself.

A tip: Only halve the array once it is just a quarter full. If you halve it as soon as it is half full, it is full afterward – and the very next push() copies it into a larger array again.

The StackDemo program shows how to use BoundedArrayStack and ArrayStack.

Outlook

In the next part of the series, you will learn about a variant that is based not on an array but on a linked list and thus grows fully automatically with each push() and shrinks again with each pop().