0%

使用递归逆序一个栈

题目

如何仅用递归函数和栈逆序一个栈

思路

递归函数一,将 stack 栈底的元素返回并且移除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
* 获取栈底元素
*
* @param stack 传入的栈
* @param <E> 返回的元素类型
* @return 栈底元素
*/
private static <E> E getAndRemoveLastElement(Stack<E> stack) {

E result = stack.pop();

if (stack.isEmpty()) {
return result;
} else {
E last = getAndRemoveLastElement(stack);
stack.push(result);
return last;
}

}

递归函数二,逆序一个栈,会调用到上面提到的 getAndRemoveLastElement 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
* 逆序一个栈
*
* @param stack 被操作的栈
* @param <E> 栈中元素类型
*/
public static <E> void reverse(Stack<E> stack) {

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

E element = getAndRemoveLastElement(stack);
reverse(stack);

stack.push(element);

}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Main {

public static void main(String[] args) {

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

for (int i = 1; i <= 5; i++) {
testStack.push(i);
}

StackReverseUtil.reverse(testStack);
}
}