仅用递归函数和栈操作逆序一个栈

【题目】

一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为 1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实现，不能用其他数据结构。

【思路】

要求只能用递归函数实现，需要设计两个函数，函数一实现返回栈底元素并移除；函数二实现逆序栈，需要使用函数一。

说明：图片来自左神的程序代码面试指南，仅供学习使用。

函数一：

//返回栈底元素并移除public static int getAndRemoveLastElement(Stack<Integer> stack){    int res = stack.pop();    if(stack.isEmpty()){        return res;    }else{        int last = getAndRemoveLastElement(stack);        stack.push(res);        return last;    }}

函数二：

//逆序栈public static void reverse(Stack<Integer> stack){	if(stack.isEmpty()){		return ;	}	int i = getAndRemoveLastElement(stack);	reverse(stack);	stack.push(i);}

【代码】

package keafmd.accumulate.codeinterviewguide.reversestack;import java.util.Stack;/** * Keafmd * * @ClassName: ReverseStack * @Description: 使用函数逆序栈 * @author: 牛哄哄的柯南 * @date: 2022-06-22 11:01 */public class ReverseStack {    //返回栈底元素并移除    public static int getAndRemoveLastElement(Stack<Integer> stack){        int res = stack.pop();        if(stack.isEmpty()){            return res;        }else{            int last = getAndRemoveLastElement(stack);            stack.push(res);            return last;        }    }    //逆序栈    public static void reverse(Stack<Integer> stack){        if(stack.isEmpty()){            return ;        }        int i = getAndRemoveLastElement(stack);        reverse(stack);        stack.push(i);    }    public static void main(String[] args) {        Stack<Integer> stack = new Stack<>();        for(int i=1;i<=5;i++){            stack.push(i);        }        System.out.print("逆序前：");        while (!stack.isEmpty()){            System.out.print(stack.pop()+" ");        }        System.out.println();        for(int i=1;i<=5;i++){            stack.push(i);        }        reverse(stack);        System.out.print("逆序后：");        while (!stack.isEmpty()){            System.out.print(stack.pop()+" ");        }        System.out.println();    }}

效果：

逆序前：5 4 3 2 1 逆序后：1 2 3 4 5 Process finished with exit code 0