java 通用堆栈实现

Generic stack implementation

提问by MAA

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

第 40 行在 push 方法中

        array[top] = element;

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

附带问题：有什么方法可以抑制构造函数中的警告？:)

回答by clstrfsck

The underlying issue is type erasure. The relevant implications of this means that an instance of the Stackclass 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].

根本问题是类型擦除。这意味着Stack该类的实例在运行时不知道它的类型参数。这就是您不能在这里使用最自然的解决方案的原因，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 Teither. In the code shown the elements are of type StackArray, which is probably not what you intended.

您已尝试通过使用 创建数组来解决此问题Array.newInstance(...)，但不幸的是，此数组也没有类型元素T。在显示的代码中，元素的类型为StackArray，这可能不是您想要的。

One common way of dealing with this is to use an array of Objectinternally to Stack, and cast any return values to type Tin accessor methods.

处理这个问题的一种常见方法是在Object内部使用一个数组to Stack，并将任何返回值转换T为访问器方法的类型。

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 maxSizeis never assigned a new value. You don't really need to keep track of maxSize, as you could just use array.length.

另请注意，您在从未分配新值的resizeArray()方法中存在错误maxSize。您实际上并不需要跟踪maxSize，因为您可以只使用array.length.

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

我认为peek()原始代码中堆栈为空时也存在问题。

回答by Sean F

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

您的代码创建了 StackArray 的数组，然后您尝试将 Character 对象放入其中，就像您在执行以下操作一样：

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