题解 | #用递归函数和栈逆序一个栈#
用递归函数和栈逆序一个栈
http://www.nowcoder.com/practice/1de82c89cc0e43e9aa6ee8243f4dbefd
思路
使用递归的方法去逆序一个栈，主要分为两步：
-
使用递归的方法找到栈 栈底 的元素，并返回
-
使用递归的方式，将元素进行逆置操作，涉及到逆序：要先递归，再操作
1. 递归寻找栈底的元素
-
递归函数有返回值，因此函数可以逐层返回需要的值
return getAndRemoveLastElem(stack) -
递归的结束条件： 当栈为空的时候，结束递归，并返回上一个值，此时的处理是：先将值取出，在判断栈的情况
-
递归的操作顺序，由于是找 栈底 的元素，因此是递归先序的方式; 递归结束之后，再将原来的元素放回
code:
public static <E> E getAndRemoveLastElem(Stack<E> stack){
// 查找最后一个元素
E elem = stack.pop();
// 最后一个，返回结果
if (stack.empty()) {
return elem;
} else {
// 如果不是最后一个，则继续寻找，并把刚刚取出的元素放回
E last = getAndRemoveLastElem(stack);
stack.push(elem);
return last;
}
}
2. 递归向栈中加入元素
-
首先查找元素，找到元素之后再看递归的操作
-
递归函数的返回值： 由于只是对栈进行操作，无返回值
-
递归函数的结束条件： 这个结束的条件比较难想，由于是向栈中添加元素，栈满了才结束，但是这个不是递归结束的条件；如何确定呢？在栈中添加元素之前，是将栈低的元素取出来，取完了就该向栈中添元素了，此时为栈递归的结束条件
-
递归的操作顺序，只有本地的栈空了才能向其中添加元素，所以先递归的查找栈低的元素，之后再向栈中添加元素，形成一个 对称的U型结构
code:
public static <E> void reverseStack(Stack<E> stack) {
// 递归结束的条件
if (stack.empty()) {
return ;
} else {
// 先找到最后的元素，递归再去寻找， 最后找不到了， 从最后开始push到stack中
E last = getAndRemoveLastElem(stack);
// 倒序插入的时候， 先递归，再操作
reverseStack(stack);
stack.push(last);
}
}
查看22道真题和解析
