题目：

一个栈依次压入 1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1.将这个栈转置后，从栈顶到栈底的1、2、3、4、5，也就是实现栈中元素的逆序。

要求：

只能使用递归函数，不能使用其他数据结构

思路：

我们需要设计两个递归方法
递归函数一：用来把栈底元素返回并移除

getAndRemoveLastElement()方法的示意图.png

递归函数二：也就是题目要求写的递归函数，逆序一个栈

reverse()方法的示意图.png

代码演示

package com.itz.zcy.stackAndQueue;

import java.util.Stack;

/**
 * 一个栈依次压入 1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1.将这个栈转置后，
 * 从栈顶到栈底的1、2、3、4、5，也就是实现栈中元素的逆序。
 * 只能使用递归函数，不能使用其他数据结构
 */
public class ReverseStack {

    private static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) {
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        reverse(stack);
        for (int i=0;i<5;i++){
            System.out.println(stack.pop());
        }
    }

    /**
     * 该方法返回栈底元素并移除
     *
     * @param stack 要查找的栈
     * @return 返回的栈底元素
     */
    private 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;
        }

    }

    /**
     * 栈逆序方法
     * @param stack 需要逆序的栈
     */
    public static void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int i = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(i);
    }
}

总结

该方法实现较为简单，使用递归对空间和时间就是一个考验

文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！