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?

• njzk2: in data[top--] = null;. The top-- is part of the stack core implementation (if you don't do it it does not work), while data[...] = null is not mandatory, and is just cleaning things to make sure memory can be freed. You should split those 2.

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);

• SirPython: Welcome to Code Review! Good job on your first answer

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

• user2357112: It seems like you're trying to mimic the standard library Stack class too closely. Built-in synchronization was a mistake; you very rarely need it, and when you do, it's not enough. There's a reason they abandoned that design decision in the Java Collections Framework. Also, if you're going to throw a standard library exception, NoSuchElementException is probably the way to go.
• user2357112: Really, the big missing improvement is automatic resizing.
• Vogel612: @user2357112 the point of making a stack is that it does not resize. How would a StackOverflowError else occur? While you're right about "built-in synchronization ir rarely needed", it still should be documented whether a class is thread-safe or not. A Stack can (and probably will) be used as a way to move work between threads. Suddenly that issue becomes relevant then. Also a NoSuchElementException generally has a different purpose. The javadoc explicitly states it's used for nextElement() in Enumeration so there's that.
• user2357112: The Javadoc is out of date. NoSuchElementException is the exception thrown by methods like Deque.removeLast and Iterator.next when there is no element to return; it's the Java Collections Framework's exception of choice for representing that a requested element does not exist. A StackOverflowError has nothing to do with this kind of stack; it means the call stack has overflowed. Both the built-in Stack class and the newer ArrayDeque auto-resize, and the OP seems to see the fixed size of his Stack as a limitation, rather than a deliberate choice.
• Vogel612: @user2357112 then write an answer :)