Generic stack implementation

Question

I'm trying to implement a generic stack.

Here's the interface

package stack;

public interface Stack<T>{
    void push(T number);
    T pop();
    T peek();
    boolean isEmpty();
    boolean isFull();
}

Here's the class

package stack;

import java.lang.reflect.Array;
import java.util.EmptyStackException;

public class StackArray <T> implements Stack<T>{
    private int maxSize;
    private T[] array;
    private int top;

    public StackArray(int maxSize) {
        this.maxSize = maxSize;
//        @SuppressWarnings("unchecked")
        this.array = (T[]) Array.newInstance(StackArray.class, maxSize);
        this.top = -1;
    }

    private T[] resizeArray() {
        /**
         * create a new array double the size of the old, copy the old elements then return the new array */
        int newSize = maxSize * 2;
        T[] newArray = (T[]) Array.newInstance(StackArray.class, newSize);
        for(int i = 0; i < maxSize; i++) {
            newArray[i] = this.array[i];
        }
        return newArray;
    }

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

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

    public void push(T element) {
        if(!this.isFull()) {
            ++top;
            array[top] = element;
        }
        else {
            this.array = resizeArray();
            array[++top] = element;
        }
    }

    public T pop() {
        if(!this.isEmpty())
            return array[top--];
        else {
            throw new EmptyStackException();
        }
    }

    public T peek() {
        return array[top];
    }
}

Here's the Main class

package stack;


public class Main {
    public static void main(String[] args) {
        String word = "Hello World!";
        Stack <Character>stack = new StackArray<>(word.length());

//        for(Character ch : word.toCharArray()) {
//            stack.push(ch);
//        }

        for(int i = 0; i < word.length(); i++) {
            stack.push(word.toCharArray()[i]);
        }

        String reversedWord = "";
        while(!stack.isEmpty()) {
            char ch = (char) stack.pop();
            reversedWord += ch;
        }
        System.out.println(reversedWord);

    }
}

The error is

Exception in thread "main" java.lang.ArrayStoreException: java.lang.Character
    at stack.StackArray.push(StackArray.java:40)
    at stack.Main.main(Main.java:14)

line 40 is in the push method

        array[top] = element;

Side Question: Any way to suppress the warning in the constructor? :)

Solution 1

The underlying issue is type erasure. The relevant implications of this means that an instance of the Stack class doesn't know it's type arguments at run-time. This is the reason why you can't just use the most natural solution here, array = new T[maxSize].

You've tried to work around this by creating an array using Array.newInstance(...), but unfortunately this array does not have elements of type T either. In the code shown the elements are of type StackArray, which is probably not what you intended.

One common way of dealing with this is to use an array of Object internally to Stack, and cast any return values to type T in accessor methods.

class StackArray<T> implements Stack<T> {
    private int maxSize;
    private Object[] array;
    private int top;

    public StackArray(int maxSize) {
        this.maxSize = maxSize;
        this.array = new Object[maxSize];
        this.top = -1;
    }

    // ... lines removed ...

    public T pop() {
        if(this.isEmpty())
            throw new EmptyStackException();
        return element(top--);
    }

    public T peek() {
        if(this.isEmpty())
            throw new EmptyStackException();
        return element(top);
    }

    // Safe because push(T) is type checked.
    @SuppressWarnings("unchecked")
    private T element(int index) {
        return (T)array[index];
    }
}

Note also you have a bug in the resizeArray() method where maxSize is never assigned a new value. You don't really need to keep track of maxSize, as you could just use array.length.

I think there is also an issue with peek() when the stack is empty in the original code.

Solution 2

Your code creates arrays of StackArray, and then you try to stick Character objects in it, just as if you were doing this:

static void add(Object arr[], Object o) {
    arr[0] = o;
}

public static void main(String[] args) {
    StackArray stack[] = new StackArray[1];
    Character c = 'x';
    add(stack, c);
}

Comments

[iMysak]

Didn't you want write T[] array = new T[maxsize]; instead of (T[]) Array.newInstance(StackArray.class, maxSize); ?

[jlordo]

Array.newInstance(StackArray.class, maxSize); will create an Array for StackArray elements. You're trying to put a Character in that array and that is not possible.

[iMysak]

please take a look on stackoverflow.com/q/20557762/814304

[Lew Bloch]

Use of newInstance is the fundamental issue. Just declare an Object[] and use an unsafe T[] cast along with an @SuppressWarnings annotation, being sure to add the mandatory associated code comment explaining why it's safe.

[MAA]

Thank you very for the extra bugs. As to the original problem, I'm never comfortable with using Object, so I kept the array as an array of T, but assigned an array of Object to it in the constructor (after casting) like @Lew Bloch suggested. Maybe it's the same thing tho:)