【算法】用递归的方法逆序输出或倒置一个栈

2023-07-29 137

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【算法】用递归的方法逆序输出或倒置一个栈

前言

我们知道，栈是先进先出的，也就是如果一个栈的输入数据为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));
    }
}