java - 通用堆栈实现

Question

我正在尝试实现一个通用堆栈。

这是界面

package stack;

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

这是类

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

这是主类

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

    }
}

错误是

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

第40行在push方法中

        array[top] = element;

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

Answer 1

根本问题是类型删除。这意味着 Stack 类的实例在运行时不知道它的类型参数。这就是为什么您不能在这里只使用最自然的解决方案 array = new T[maxSize] 的原因。

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

处理此问题的一种常见方法是在内部使用 Object 数组来 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];
    }
}

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

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