逆序输出一个栈--java实现

短命女 2022-10-09 02:51 159阅读 0赞

给出一个栈，需要逆序输出，即把此栈反过来,可以不加限制条件，这种情况下有多种实现实现思路；也可以加一些限制条件，比如不能申请额外的内存空间，只允许使用递归函数实现等等，当然限制条件越多，实现的思路越少。这里我们分享两种实现方案：

1、不加限制条件：用个list集合做介质，核心代码如下

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @author wanghuainan
     * @date 2021/6/23 10:35
     */
    public class NanDaoReverseStack {
    
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
            stack.push(1);
            stack.push(2);
            stack.push(3);
    
            test1(stack);
            while (!stack.isEmpty()){
                System.out.print(stack.pop() + " ");
            }
            System.out.println();
        }
    
        private static void test1(Stack<Integer> stack) {
            List<Integer> list = new ArrayList<>();
            while (!stack.isEmpty()){
                Integer i = stack.pop();//依次弹出
                list.add(i);//list是头插法  3 2 1
            }
            for(int i = 0;i < list.size();i++){
                Integer integer = list.get(i);
                stack.push(integer);//重新入栈 顺序为3 2 1 ，即弹出顺序 1 2 3
            }
        }
    
    }

执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

2、使用递归函数且不能申请额外空间：核心代码如下

import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @author wanghuainan
     * @date 2021/6/23 10:35
     */
    public class NanDaoReverseStack {
    
        public static void main(String[] args) {
            Stack<Integer> stack = new Stack<>();
            stack.push(1);
            stack.push(2);
            stack.push(3);
    
            test2(stack);
            while (!stack.isEmpty()){
                System.out.print(stack.pop() + " ");
            }
            System.out.println();
        }
    
        private static void test2(Stack<Integer> stack) {
            if(stack.isEmpty()){
                return;
            }
            Integer i = t2(stack);
            test2(stack);//继续去弹出栈底元素
            stack.push(i);//
        }
    
    
        private static Integer t2(Stack<Integer> stack) {
            Integer result = stack.pop();
            if(stack.isEmpty()){
                return result;//栈底元素正式弹出
            }else {
                Integer last = t2(stack);//栈底元素弹出
                stack.push(result);// 栈底上面的元素下到最底层
                return last;// 栈底元素移除并返回
            }
    
        }
    
       
    }

执行结果：

![20210623134025342.png][]

到此，逆序输出一个栈的算法思想分享完成，大家多思考，勤练习，定会进很快！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/4c0aedd42043457aa47e6781313a3c95.png
[20210623134025342.png]: /images/20221005/430bd23a8f86441ba380e8454e5134fa.png