用递归逆序栈

技术文章 1年前 (2020) 完美者
314 0

标签:pstack   main   coder   otto   imp   href   nal   asn   vat   

一个栈依次压入1,2,3,4,5,那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现栈中元素的逆序,但是只能用递归函数来实现,不能用其他数据结构。

题目地址:用递归函数和栈逆序一个栈


import java.util.Scanner;
import java.util.Stack;

public class Main {

    private static int getAndPopStackBottom(Stack<Integer> stack) {

        Integer top = stack.pop();

        if (stack.isEmpty()) {
            return top;
        }

        int bottom = getAndPopStackBottom(stack);

        stack.push(top);

        return bottom;

    }

    private static void reverseStack(Stack<Integer> stack) {

        if (stack.isEmpty()) {
            return;
        }

        int bottom = getAndPopStackBottom(stack);

        reverseStack(stack);

        stack.push(bottom);

    }

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        while (in.hasNext()) {

            int n = in.nextInt();

            int[] tmpArr = new int[n];

            for (int i = 0; i < n; ++ i) {
                tmpArr[i] = in.nextInt();
            }

            Stack<Integer> rawStack = new Stack<>();

            for (int i = n - 1; i >= 0; i --) {
                rawStack.push(tmpArr[i]);
            }

            reverseStack(rawStack);

            System.out.print(rawStack.pop());
            for (int i = 1; i < n; ++ i) {
                System.out.print(" " + rawStack.pop());
            }
            System.out.println();
        }

    }
}

用递归逆序栈

标签:pstack   main   coder   otto   imp   href   nal   asn   vat   

原文地址:https://blog.51cto.com/tianyiya/2530941

版权声明:完美者 发表于 2020-09-17 20:32:40。
转载请注明:用递归逆序栈 | 完美导航

暂无评论

暂无评论...