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

【题目】

一个栈依次压入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