Implementing ArrayStack

Here is the Stack interface:

public interface Stack<T> {
  void push(T item);  // throws IllegalArgumentException if item is null
  void pop();         // throws NoSuchElementException if the stack is empty
  T top();            // throws NoSuchElementException if the stack is empty
  boolean isEmpty();
}

ArrayStack<T> implements the Stack<T> interface:

import java.util.NoSuchElementException;

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

  private T[] arr;
  private int size;  // number of items on the stack

  @SuppressWarnings("unchecked")
  public ArrayStack() {
    arr = (T[]) new Object[10];
    size = 0;
  }

  // Doubles the capacity of arr, keeping the items in place.
  private void grow() { /* given */ }

  // push, pop, top, and isEmpty go here
}

Solution

The last used index, size - 1. Adding or removing there moves no other item, so it is $O (1)$ . With the top at index 0, every push and pop would shift all the other items, which is $O (n)$ .

Solution

public boolean isEmpty() {
  return size == 0;
}

public T top() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  return arr[size - 1];
}

Solution

public void pop() {
  if (isEmpty()) {
    throw new NoSuchElementException();
  }
  size--;
  arr[size] = null;
}

Solution

public void push(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (size == arr.length) {
    grow();
  }
  arr[size] = item;
  size++;
}

Solution

isEmpty, top, and pop are $O (1)$ : each reads or writes size and at most one slot. push is amortized $O (1)$ : it writes one slot, and the $O (n)$ grow runs only when the array is full, which doubling makes rare.