不使用 Java API 反转堆栈

Question

我想实现一个反转堆栈的反转方法。我认为解决方案是递归。我尽力了，但没有用。谁能告诉我我的错误在哪里？

public class Stack<E> {

    private final E value;
    private final Stack<E> next;

    private Stack(E value, Stack<E> next) {
        this.value = value;
        this.next = next;
    }

    public static <E> Stack<E> create() {
        return null;
    }
    public static <E> Stack<E> push(Stack<E> a, E e) {
        Stack<E> erg = new Stack<E>(e,a);
        return erg;
    }

    public static <E> Stack<E> pop(Stack<E> a) { //pop(push(s,e) = s
        if (a == null) {
            return Stack.<E>create();
        }
        else if (a.value == null){
            return Stack.<E>create();
        }
        else {
            return a.next;
        }
    }
    public static <E> E top(Stack<E> a) {
        if (a == null) {
            return null;
        }
        else if (a.value == null){
            return null;
        }
        else {
            return a.value;
        }
    }
    public static <E> boolean isEmpty(Stack<E> a) {
        if (a == null) {
            return true;
        }
        else if (a.value == null) {
            return true;
        }
        else {
            return false;
        }
    }
    public static <E> Stack<E> reverse(Stack<E> s) {
        Stack<E> top = Stack.<E>pop(s);
        if (Stack.<E>isEmpty(s)) {
            return top;
        } else {
            Stack<E> bottom = reverse(s);
            Stack.<E>push(top, null);
            return bottom;
        }
    }
}

不允许我使用 Java API 中的类；我不允许添加更多类或方法或属性。

Answer 1

使用另一个堆栈来反转堆栈。

public static <E> Stack<E> reverse(Stack<E> s) {
    Stack<E> reversedStack = new Stack<E>(null, null);
    while(!Stack.<E>isEmpty(s) {
        Stack.<E>push(reversedStack, s.value);
        s = Stack.<E>pop(s));
    }
    return reversedStack;
}

Answer 2

这是我的做法。我正在使用属于 API 的 Stack，但只要堆栈具有 push 和 pop，任何实现都应该有效。

在反向方法中创建一个新堆栈。
当您从原始堆栈中弹出一个值时，将其推入新堆栈。
return新堆栈

Stack<Integer> stack = new Stack<>();
for (int i = 1; i < 6; i++) {
    stack.push(i);
}

System.out.println(stack);
stack = reverse(stack);
System.out.println(stack);
    
    
public static <T> Stack<T> reverse(Stack<T> stack) {
    Stack<T> reversed = new Stack<>();
    while (!stack.isEmpty()) {
        reversed.push(stack.pop());
    }
    return reversed;
}

版画

[1, 2, 3, 4, 5]
[5, 4, 3, 2, 1]

不使用 Java API 反转堆栈

Reversing a Stack without using Java API

java

generics

recursion

linked-list

stack