ArrayStack in Java

An ArrayStack stores elements in an array and maintains the index top. push writes at top and increments the index. pop decrements top and returns the value. The capacity is the length of the array.

Advantage: $O(1)$ amortized operations and good locality. Disadvantage: fixed or costly doubling of capacity.

Implementation detail: top points to the next free slot or the top element. The class must consistently maintain this.

Task: Implement push and pop for an int stack with fixed capacity and exceptions for overflow and underflow.

Where used

Teaching implementation for what the JVM provides internally and what ArrayDeque offers as a stack replacement. In production, prefer Deque methods (push/pop at the same end) instead of a custom array class unless the task requires control over capacity and error codes.

Depth

An array-based LIFO storage holds occupied elements in a contiguous prefix. size conveniently refers to both the number of elements and the next free index. Insertion writes first at this position and then increments the counter.

If the array is full, a larger array is created, and the occupied prefix is copied. Individual expansions are expensive, but they occur less frequently with geometric growth. Over a long sequence of operations, the average extra work per insertion remains limited.

When removing, the freed reference should be set to null. Otherwise, the internal array keeps an object accessible that is logically no longer present. This is not a functional error but can unnecessarily bind memory.

Difficulty levels

1. Track push, pop, and peek with a size invariant.
2. Analyze geometric growth across multiple capacity thresholds.
3. Explain stale references and generic array issues in Java.

Pitfalls

After reducing size, the old cell must be deleted. In generics, an unconsidered type cast can lead to warnings or unsafe runtime errors.