前言
我们知道，栈是先进先出的，也就是如果一个栈的输入数据为1，2，3，4，5，那么他的输出数据为5，4，3，2，1。
而如果我们想要以队列的方式先进先出一个栈，那么我们就需要用到两个栈，或者，按照标题所说的，我们可以使用递归的方式，来使用一个栈来逆序输出栈中的数据。
同时，我们也可以考虑逆序这个栈，也可以做到先进先出的效果。
思路分析
递归函数1：将栈stack的栈底元素移除并且返回。
具体方法如下：
package com.base.learn.stack; import java.util.Stack; /** * @author: 张锦标 * @date: 2023/5/27 15:28 * ReverseStack类 * 使用递归和栈，来反转输出一个栈 */ public class ReverseStack { private static Stack<Integer> stack = new Stack<>(); public static int getAndRemoveLastElement(Stack<Integer> stack){ int result = stack.pop(); if (stack.isEmpty()){ return result; }else{ int last = getAndRemoveLastElement(stack); stack.push(result); return last; } } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(getAndRemoveLastElement(stack)); System.out.println(getAndRemoveLastElement(stack)); System.out.println(getAndRemoveLastElement(stack)); System.out.println(getAndRemoveLastElement(stack)); System.out.println(getAndRemoveLastElement(stack)); } }
这里我并不讲解或者画图它是如何做到的，这里建议你直接debug。
递归函数2：逆序一个栈。
我们可以基于递归函数1，递归函数1已经帮我们拿到了最接近栈底的元素了，那么我们只需要拿到这个元素的时候，将其塞入到队列中即可。
代码如下：
package com.base.learn.stack; import java.util.Stack; /** * @author: 张锦标 * @date: 2023/5/27 15:28 * ReverseStack类 * 使用递归和栈，来反转输出一个栈 */ public class ReverseStack { private static Stack<Integer> stack = new Stack<>(); public static int getAndRemoveLastElement(Stack<Integer> stack){ int result = stack.pop(); if (stack.isEmpty()){ return result; }else{ int last = getAndRemoveLastElement(stack); stack.push(result); return last; } } public static void reverse(Stack<Integer> stack){ if (stack.isEmpty()){ return ; } int i = getAndRemoveLastElement(stack); System.out.println(i); reverse(stack); stack.push(i); } public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack); reverse(stack); System.out.println(stack); //System.out.println(getAndRemoveLastElement(stack)); //System.out.println(getAndRemoveLastElement(stack)); //System.out.println(getAndRemoveLastElement(stack)); //System.out.println(getAndRemoveLastElement(stack)); //System.out.println(getAndRemoveLastElement(stack)); } }
简单讲解
getAndRemoveLastElement方法通过递归的方式，直接访问到了栈的最下层的元素，并且通过递归的方式，出栈这个栈底元素之后，再把其上面的元素再继续压回去，因此做到了不修改栈结构，不使用额外空间的方式来输出栈底元素。
reverse方法则依赖于这个第一个方法，我们知道第一个方法会先输出栈底元素，那么，当reverse方法遍历到最深的时候，其实是得到栈顶元素的时候，因为是逆序的！
所以，当第一个方法递归结束，我们得到的是栈顶的元素，并且第一个方法的每一次调用都会从栈底删除一个元素，那么当第一个方法的递归调用结束的时候，栈以空，那么此时我们拿着栈顶元素，放入到栈中，从而得到逆序栈！
