如何使用递归在堆栈中找到一个值并将其放在顶部？

Question

如何使用递归在堆栈中搜索一个值并将其放在顶部？我使用迭代想到了这段代码：

package pila2;
import java.util.Stack;

public class search {

public static void main(String[] args) {
    Stack<Integer> st1 = new Stack<>(); //Original stack
    Stack<Integer> st2 = new Stack<>(); //Stack used to store removed values
    int container; //Holds the current popped value
    int n; //Value being searched
    int st1Tam; //Stores the size of st1
    int st2Tam; //Stores the size of st2
    
    st1.push(3);
    st1.push(8);
    st1.push(1);
    st1.push(6);
    
    n = 3;
    
    do { //Main loop checks st1
        container = st1.pop();
        if (container == n) { //Value found
            if(st2.size() == 0) {//if second stack is empty the found value is stacked
                st1.push(container);
            }else {//st2 is popped and values stored in st1
                do {
                    st1.push(st2.pop());
                    st2Tam = st2.size();
                }while(st2Tam > 0);
                st1.push(container);
            }
            break;
        }
        st2.push(container);
        st1Tam = st1.size();
    }while(st1Tam > 0);
    
    System.out.println(st1);
    System.out.println(st2);
}
}

我也在想如何改进原来的代码

Answer 1

试试这个。

void findToTop(Stack<Integer> stack, int search) {
    if (findToTopSub(stack, search))
        stack.push(search);
}

boolean findToTopSub(Stack<Integer> stack, int search) {
    if (stack.isEmpty()) return false;
    int top = stack.pop();
    if (top == search) return true;
    boolean found = findToTopSub(stack, search);
    stack.push(top);
    return found;
}

和

Stack<Integer> stack = new Stack<>();
stack.push(3);
stack.push(8);
stack.push(1);
stack.push(6);
System.out.print(stack);
findToTop(stack, 3);
System.out.println(" -> " + stack);

输出：

[3, 8, 1, 6] -> [8, 1, 6, 3]

如何使用递归在堆栈中找到一个值并将其放在顶部？

How to find a value in a stack and put it on top using recursion?

java

iteration

recursion

stack