package com.jiucaiyuan.net.question;



import java.util.Stack;



/**

 * 【问题】不使用额外空间逆序一个栈：给你一个栈，请你逆序这个栈，

 * 不能申请额外的数据结构，只能使用递归函数，如何实现？

 * 【思路】通过用递归，利用栈帧局部变量保存，未主动额外申请空间

 *

 * @Author jiucaiyuan  2022/4/22 22:24

 * @mail services@jiucaiyuan.net

 */



public class ReverseStackNoExtraSpace {

    /**

     * 未申请额外空间（利用递归栈帧）逆序一个栈

     *

     * @param stack 待逆序的栈

     */

    public static void reverse(Stack<Integer> stack) {

        if (stack.isEmpty()) {

            return;

        }

        int i = getLastElement(stack);

        reverse(stack);

        stack.push(i);

    }



    /**

     * 功能：返回stack栈底元素，其他元素仍然在栈中，原来的顺序

     * 如(左侧是栈顶，右侧是栈底)：栈中入参[1,2,3]，返回3，栈变成[1,2]

     *

     * @param stack

     * @return 返回stack当前栈底元素

     */

    public static int getLastElement(Stack<Integer> stack) {

        int result = stack.pop();

        if (stack.isEmpty()) {

            return result;

        } else {

            int last = getLastElement(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);

        stack.push(6);

        System.out.println(stack);

        reverse(stack);

        System.out.println(stack);

    }





}