用递归函数实现栈的逆序

题目描述

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

输入描述:

输入数据第一行一个整数N为栈中元素的个数。
接下来一行N个整数$x_i$表示从栈顶依次到栈底的每个元素。

输出描述:

输出一行表示栈中元素逆序后的每个元素

示例1

输入
5
1 2 3 4 5

输出
5 4 3 2 1

解题

/*
解题思路：
定义两个递归函数，一个函数用来获取栈元素，另一个函数负责将栈底元素重新压入
*/

import java.util.*;
import java.io.*;
 
public class Main{
     
    private static Stack<Integer> stack =new Stack<>();
     
    public static void main(String[] args) throws IOException{
         
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(in.readLine());
        StringBuilder result = new StringBuilder();
        for(String i:in.readLine().split(" ")){
            stack.push(Integer.parseInt(i));
        }
        reverse(stack);
        //以上的代码只是处理成题目要求的栈，下面才是反转及打印
        
        reverse(stack);
        while(!stack.isEmpty())
            System.out.print(stack.pop()+" ");
    }
    
    private static int getAndRemoveLastVar(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        }else{
            //获取栈底元素
            int last = getAndRemoveLastVar(stack);
            //将上面的元素重新压入
            stack.push(result);
            //返回栈底元素
            return last;
        }
    }
    
    private static void reverse(Stack<Integer> stack){
        if(stack.isEmpty())
            return;
        else{
            //获取栈底元素
            int i = getAndRemoveLastVar(stack);
            reverse(stack);
            //将栈底元素重新压入
            stack.push(i);
        }
    }

}