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

比眉伴天荒 2024-03-16 09:39 108阅读 0赞

#### 文章目录 ####

*  前言
 *  思路分析
 *  简单讲解

## 前言 ##

我们知道，栈是先进先出的，也就是如果一个栈的输入数据为1，2，3，4，5，那么他的输出数据为5，4，3，2，1。  
而如果我们想要以队列的方式先进先出一个栈，那么我们就需要用到两个栈，或者，按照标题所说的，我们可以使用递归的方式，来使用一个栈来逆序输出栈中的数据。  
[两个栈制作一个队列][Link 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));
        }
    }

![在这里插入图片描述][cac01e07436946a890ee0377e19df9cc.png]

## 简单讲解 ##

getAndRemoveLastElement方法通过递归的方式，直接访问到了栈的最下层的元素，并且通过递归的方式，出栈这个栈底元素之后，再把其上面的元素再继续压回去，因此做到了不修改栈结构，不使用额外空间的方式来输出栈底元素。

reverse方法则依赖于这个第一个方法，我们知道第一个方法会先输出栈底元素，那么，当reverse方法遍历到最深的时候，其实是得到栈顶元素的时候，因为是逆序的！  
所以，当第一个方法递归结束，我们得到的是栈顶的元素，并且第一个方法的每一次调用都会从栈底删除一个元素，那么当第一个方法的递归调用结束的时候，栈以空，那么此时我们拿着栈顶元素，放入到栈中，从而得到逆序栈！

[Link 1]: https://blog.csdn.net/Zhangsama1/article/details/130901488?spm=1001.2014.3001.5502
[cac01e07436946a890ee0377e19df9cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/7c90e9147229404a8e4f0dcce828fa7e.png