[程序员代码面试指南]栈和队列-仅用递归函数和栈操作来逆序一个栈(递归)

问题描述

如题。
输入 栈12345
输出 栈54321

解题思路

用两个递归函数：

• 第一个可以将栈底元素弹出
• 第二个借助第一个可以实现栈逆序

代码

import java.util.Stack;

public class Main {
	public static void main(String args[]) {
		Stack<Integer> s=new Stack<>();
		s.push(1);
		s.push(2);
		s.push(3);
		for(int val:s) {
			System.out.println(val);
		}
		
		reverse(s);
		for(int val:s) {
			System.out.println(val);
		}
	}
	
	public static int popBottom(Stack<Integer> s) {
		int val=s.pop();//出栈
		if(s.empty()) {//返回条件
			return val;
		}
		int bottomVal=popBottom(s);
		s.push(val);//再入栈
		return bottomVal;
	}
	
	public static void reverse(Stack<Integer> s) {
		if(s.empty()) {//返回条件
			return;
		}
		int val=popBottom(s);//出栈
		reverse(s);
		s.push(val);//再入栈
	}
}