一道比较有意思的算法题——原地逆序一个栈

一道比较有意思的算法题——原地逆序一个栈

今天看到一道很有意思的题,解完以后不得不惊叹解法设计的精妙之处,于是在这里记录一下

【题目】

一个栈依次压入1,2,3,4,5,那么从栈顶到栈底分别为5,4,3,2,1。逆序这个栈即要求转置后,从栈顶到栈底为1,2,3,4,5。但你不能使用其他的数据结构,只允许使用递归函数实现。

【解答】

本题考查栈的操作和递归函数的设计 我们拆分为2步
首先设计一个递归函数实现功能从栈底“pop”:将栈底的元素返回并删除(保持其他元素顺序不变),代码如下:

public static int popBottom(LinkedList<Integer> stack){
	int result = stack.pop();
	if(stack.isEmpty()){
		return result;
	}else{
		int last = popBottom(stack);
		stack.push(result);
		return last;
	}
}

popBottom函数调用栈

然后实现递归函数逆序一个栈,该方法将基于上面的popBottom实现,具体过程见下文的reverse方法

public static void reverse(LinkedList<Integer> stack){
	if(stack.isEmpty()){
		return;
	}
	int i = popBottom(stack);
	reverse(stack);
	stack.push(i);
}

reverse方法调用栈

最精妙的地方在于拆分成了2个递归函数,
并且在popBottom方法中通过int last保证了最底层的bottom值通过last一直传递回顶层,而每一层内执行poppush方法保持原样;
reverse方法中push的时机注意是在执行下层之后再重新push