用递归函数和栈操作逆序一个栈

发布于 — 2019 年 10 月 15 日
#栈

题目：

实现一个函数，将栈内元素的顺序进行翻转。如果当前栈内元素顺序为：1，2，3，4，5. 在调用这个函数后顺序为：5，4，3，2，1.

要求：

只能使用递归函数来实现，不能使用其他的数据结构。

解答：

该函数需要将栈内的元素顺序进行反转, 并且只能使用递归来实现.

我们需要分为两部分来实现:

  1. 实现一个通过递归来获取当前栈内最后一个元素的函数, 并保证其他元素顺序不变
  2. 递归调用获取最后一个元素的函数直至栈为空, 此时获取的元素为栈内的第一个元素, 将其插入栈中, 然后将其他元素再写会栈内. 完成逆序.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class ReverseStack {

	public void reverse(Stack<Integer> stack) {
		if (stack.isEmpty()) {
			return;
		}
		int last = getAndRemoveLatestElement(stack);
		reverse(stack);
		stack.push(last);
	}

	private int getAndRemoveLatestElement(Stack<Integer> stack) {
		Integer res = stack.pop();
		if (stack.isEmpty()) {
			return res;
		} else {
			int last = getAndRemoveLatestElement(stack);
			stack.push(res);
			return last;
		}
	}

}