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

It's pretty 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 image shows a stack with an array namedelements 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 thenumberOfElements variable. The value of this variable tells us at which position in the array we have to insert or read an element:

• Einfügen: at positionnumberOfElements
• Auslesen: at positionnumberOfElements - 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 fairly simple, as the following Java code shows (BoundedArrayStack class in GitHub):

publicclassBoundedArrayStack<E>implementsStack<E>{privatefinal Object[] elements;privateint numberOfElements;publicBoundedArrayStack(int capacity){if (capacity <1) {thrownew IllegalArgumentException("Capacity must be 1 or higher");    }    elements =new Object[capacity];  }@Overridepublicvoidpush(E item){if (numberOfElements == elements.length) {thrownew IllegalStateException("The stack is full");    }    elements[numberOfElements] = item;    numberOfElements++;  }@Overridepublic Epop(){    E element = elementAtTop();    elements[numberOfElements -1] =null;    numberOfElements--;return element;  }@Overridepublic Epeek(){return elementAtTop();  }private EelementAtTop(){if (isEmpty()) {thrownew NoSuchElementException();    }@SuppressWarnings("unchecked")    E element = (E) elements[numberOfElements -1];return element;  }@OverridepublicbooleanisEmpty(){return numberOfElements ==0;  }}Code language:Java(java)

It gets a bit more complicated when more elements are to be pushed onto the stack than the size of the array. An array cannot grow. I will show you how this works in the next chapter.

Implementing a Stack with a Variable Size Array

Instead, we must (when the array is full):

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

The following diagram represents these three steps visually:

We can do all this in Java in just one step by calling theArrays.copyOf() method. All we have to do is pass the size of the new array to the method.

Source Code for the Stack with a Variable Size Array

The following code shows a stack initially created with an array for ten elements. Each time thepush() method is called, it checks whether the array is full. If it is, thegrow() method is called.

Thegrow() method, in turn, callscalculateNewCapacity() to calculate the new size of the array. In the example, we expand the array always by a factor of 1.5. The code also specifies a maximum size for the array. If this is reached and another element is pushed, an exception is thrown (unless we got anOutOfMemoryError before).

Here is the code (classArrayStack in GitHub):

publicclassArrayStack<E>implementsStack<E>{publicstaticfinalint MAX_SIZE = Integer.MAX_VALUE -8;privatestaticfinalint DEFAULT_INITIAL_CAPACITY =10;private Object[] elements;privateint numberOfElements;publicArrayStack(){this(DEFAULT_INITIAL_CAPACITY);  }publicArrayStack(int initialCapacity){    elements =new Object[initialCapacity];  }@Overridepublicvoidpush(E item){if (elements.length == numberOfElements) {      grow();    }    elements[numberOfElements] = item;    numberOfElements++;  }privatevoidgrow(){int newCapacity = calculateNewCapacity(elements.length);    elements = Arrays.copyOf(elements, newCapacity);  }staticintcalculateNewCapacity(int currentCapacity){if (currentCapacity == MAX_SIZE) {thrownew IllegalStateException("Can't grow further");    }int newCapacity = currentCapacity + calculateIncrement(currentCapacity);if (newCapacity > MAX_SIZE || newCapacity <0/* overflow */) {      newCapacity = MAX_SIZE;    }return newCapacity;  }privatestaticintcalculateIncrement(int currentCapacity){return currentCapacity /2;  }// pop(), peek(), elementAtTop(), isEmpty() are the same as in BoundedArrayStack}Code language:Java(java)

The methodspop(),peek(),elementAtTop(), andisEmpty() are identical to those in theBoundedArrayStack presented above. I have, therefore, not printed them again.

TheArrayStack 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.

You can see howBoundedArrayStack andArrayStack can be used in theStackDemo program.

Outlook

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

If you still have questions, please ask them via the comment function. Do you want to be informed about new tutorials and articles? Thenclick here to sign up for the HappyCoders.eu newsletter.