如何递归地将栈顶元素交换到底部

Question

我想知道如何递归地将堆栈的顶部元素交换到底部。堆栈最终应如下所示：

4 (top)
3
2
1

变成

3 (top)
2
1
4

我想出了递归函数来颠倒堆栈的顺序。但我坚持只为一个人做这件事。我假设它与改变基本情况有关。

public void roll() {

    if (!isEmpty()){
        E temp = getBottom(this);
        roll();
        this.push(temp);
    }

}

private E getBottom(LinkedStack<E> p){
    E temp = p.pop();
    if (p.isEmpty()){
        return temp;
    } else {
        E temp2 = getBottom(p);
        p.push(temp);
        return temp2;
    } 
}

Answer 1

我实际上更喜欢迭代地进行，但由于您已经递归地指定，您可以通过反转堆栈然后再次部分反转来完成它。更简单的是直接将顶部元素发送到底部：

public void sendTopToBottom() {

    if (!isEmpty()){
        sendToBottom(pop());
    }

}

private void sendToBottom(E victim){
    if (isEmpty()){
        push(victim);
    } else {
        E temp = pop();
        sendToBottom(victim);
        push(temp);
    } 
}

Answer 2

你只需要交换顶部的两个元素，然后将第二个顶部元素留在外面，在交换所有元素之后再将那个元素推回去。例如：

    public void roll(Stack<Integer> stack) {
        if (stack.size() <= 1) {
            return;
        }
        Integer top1 = stack.pop();
        Integer top2 = stack.pop();
        stack.push(top1);
        roll(stack);
        stack.push(top2);
    }

如何递归地将栈顶元素交换到底部

How to recursively swap top element of stack to the bottom

java

recursion

stack

reverse

swap