本文共 1146 字，大约阅读时间需要 3 分钟。

【题目】

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

【难度】

两星

【解答】

本题我们要实现两个递归函数——getAndRemoveLastElement，reverse

1. getAndRemoveLastElement(Stack<Integer> stack)的作用是移除并返回栈底元素
2. reverse(Stack<Integer> stack)函数实现栈的逆序   

递归的思想就是把问题的规模由大变小， 但是解决问题的方法不变。

一.我们先来讲第二个函数reverse，reverse需要借助第一个函数getAndRemoveLastElement：

递归思想：

1. 先调用gerAndRemoveLastElement弹出并取得栈底元素value
2. 然后调用reverse对少了一个元素的栈进行逆序处理
3. 最后把value压入栈， 就实现了栈元素的逆序

递归终止条件：

    我们调用reverse的参数stack的规模不断缩小， 直到栈空，说明元素都移了出来， 此时返回， 就会一个一个元素压回去

【实现代码】

public static void reverse(Stack
   
     stack) {		if(stack.isEmpty()) {			return;		}else {			int value = getAndRemoveLastElement(stack);			reverse(stack);			stack.push(value);		}	}
   

二. getAndRemoveLastElement

1. 弹出并返回栈底元素， 我们用递归的思想来解决这个问题：
2. 我们先弹出栈顶元素value
3. 然后弹出并返回少了一个元素的栈的栈底元素
4. 最后把value压入栈顶

递归终止条件：

    不断调用getAndRemoveLastElement， 其参数stack的规模不断减小， 弹出最后一个元素时栈空， 说明最后一个元素就是栈底元素， 返回即可。

【实现代码】

public static int getAndRemoveLastElement(Stack
   
     stack){    int value = stack.pop()    if(stack.isEmpty()){        return value;    }    int result = getAndRemoveLastElement(stack)    stack.push(value);    return result;}
   

转载地址：http://ohaii.baihongyu.com/