栈逆序

栈逆序

要求1.用一个跟它一样的空栈实现

要求2.只用递归函数，不能用其他数据结构

题1思路：栈A栈顶元素弹出给temp，剩下的放到B中，temp入A，再把B中放回A。此时栈底的一个是逆序好的，栈A除了栈底剩下的再重复刚才的过程

class ReverseOrder{
    public void reverseOrder(Stack<Integer> s){
        int reverseNum = 0, temp = 0;//已经逆序的个数
        Stack<Integer> s1 = new Stack<Integer>();
        while(reverseNum < s.size()){
            temp = s.pop();
            while(s.size() - reverseNum > 0){
                s1.push(s.pop());
            }
            s.push(temp);
            while(!s1.isEmpty()){
                s.push(s1.pop());
            }
            reverseNum++;
        }
    }
}

题2思路：第一个递归函数用来得到栈底的元素，第二个是逆序函数

public class ReverseStackWithOnlyRecursion {

    public int getAndRemoveLastElement(Stack<Integer> s){
        int result = s.pop();
        if(s.isEmpty())
            return result;
        else{
            int last = getAndRemoveLastElement(s);
            s.push(result);
            return last;
        }
    }
    public void reverse(Stack<Integer> s){
        if(s.isEmpty())
            return;
        int i = getAndRemoveLastElement(s);
        reverse(s);
        s.push(i);
    }
}