Array-based stack data structure in Java

Question

I've recently been writing simple data structures, even though they exist in the library it helps me understand them a lot better.

public class Stack<E>
{
    private int capacity;
    private E[] data;
    private int top;

    /**
     * Default Constructor where the stack size is initially
     * set to 1000 elements.
     */
    public Stack(int capacity) {
        this.capacity = capacity;
        this.data = (E[])new Object[capacity];
        top = -1;
    }
    public Stack() {
        this(1000);
    }

    public int size() {
        return top + 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public E top() throws EmptyADTException {
        if(isEmpty())
            throw new EmptyADTException("Nothing in the stack!");
        return data[top];
    }

    public void push(E obj) {
        if(data.length == size())
            throw new IllegalStateException("Stack is full!");
        data[++top] = obj;
    }

    public E pop() throws EmptyADTException {
        if(isEmpty())
            throw new EmptyADTException("Nothing in the stack!");
        E popObj = data[top];
        data[top--] = null;
        return popObj;
    }
}

I know that there are drawbacks to using an array-based stack, because of the limited size. Although, in the long run, it is more efficient if the time per operation isn't an issue, when compared to a linked-list implementation. I've also heard of people now using something called a VList.

I was wondering, is there any way I can improve this code whilst still using an array-based stack?

Answer 1

Auto-resize.

There's nothing saying an array-based stack has to have a fixed size. The standard library Stack doesn't have a fixed size, and it's array-based. Same with ArrayDeque, the stack you should be using instead of the Stack class.

Just make a bigger array if you run out of room. You'll want to grow the array by a multiplicative factor to make sure you don't have to resize too often; you want push to be amortized constant time.

public void push(E obj) {
    if(data.length == size())
        data = Arrays.copyOf(data, 2*data.length+2); // +2 in case data.length == 0
    data[++top] = obj;
}

Get rid of the capacity instance variable.

You literally never use it.

Are those checked exceptions?

You declare throws EmptyADTException on two of your methods, which you shouldn't have to do. throws is only necessary for checked exceptions, and EmptyADTException shouldn't be a checked exception. Checked exceptions are for things that might go wrong even if the code is correct, like FileNotFoundException. If someone tries to pop from an empty stack, that's a coding error.

If your EmptyADTException is a checked exception, make it descend from RuntimeException so it's unchecked. Making it a checked exception just bloats any code that uses your stack, and the exception-swallowing catch blocks that result will actually reduce the chances that bugs are found.

Consider throwing NoSuchElementException.

It's what the Java Collections Framework throws for cases like popping from an empty stack. There's also EmptyStackException, which is what the standard library Stack throws, but I don't recommend it. Stack is old, doesn't really fit with newer additions to the Java standard library, and has old design mistakes like built-in synchronization. You shouldn't try to copy it.

Don't use the increment/decrement operators inside of a bigger expression.

Code like data[++top] = obj; requires more thought about what happens in what order than something like ++top; data[top] = obj;.

Don't try to make generic arrays.

    this.data = (E[])new Object[capacity];

This might look like it works, but that's just because type erasure prevents Java from noticing the error. What you're doing here is storing an Object[] in a variable of type E[], even though Object probably isn't E. If you ever do anything that lets Java notice the error, for example

// Inside the Stack class, so data is accessible
Integer[] ints = new Stack<Integer>(5).data;

you'll get a ClassCastException. The correct way to make a generic array is a lot of unnecessary hassle; the best way to go is generally to just make the data variable an Object[]:

public class Stack<E>
{
    private int capacity;
    private Object[] data;

and cast elements when you retrieve them from the array:

public E top() throws EmptyADTException {
    if(isEmpty())
        throw new EmptyADTException("Nothing in the stack!");
    return (E) data[top];
}

For reference, this is how you'd make a generic array correctly:

public Stack(Class<E> klass, int capacity) {
    data = Array.newInstance(klass, capacity);
    ...

and then you'd need to pass a Class object into the Stack constructor:

Stack<Integer> stack = new Stack<>(Integer.class, 10);

Answer 2

Stay close to the library

Following the principle of least surprise you should not throw EmptyADTException, but EmptyStackException

Additionally your top method should be named peek to remain close to the Library's definition.

Style notes

Your bracing style on your class is not the usual java style and also different from all the other braces you placed.

Your Javadoc for the default constructor is not on the default constructor.

The default capacity is a magic number. You should extract it to a named constant (and mention it in the class-level javadoc)

Inline unary operators are difficult to spot and thus kind of dangerous:

data[++top] = obj;
data[top--] = null;

should be split up.

Thread safety

Your class is completely vulnerable to lost updates and similar errors when accessed concurrently.

Consider a simultaneous pop and push. You may actually lose the item you just pushed in between:

    E popObj = data[top];
    data[top--] = null;

when modifying the content of data you should consider synchronizing. Alternatively you should explicitly mention this class is not threadsafe