11.1

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

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

思路

如果仍然允许使用其他栈，那么每次要取得栈底元素，然后投入到栈中
int getAndRemoveLastElement(Stack<Integer> stack)是取得栈底，并且保持栈的状态
result栈顶，依次为5,4,3,2,1，然后栈空返回1
last是得到的栈底元素，即刚刚的返回的1，最后又返回last为1
可见递归过程中last一直都是1
依次压入result，2,3,4,5，这个过程就还原了栈

代码

//反转栈
public static void reverse(Stack<Integer> stack) {
	if (stack.isEmpty()) {
		//栈空返回
		return;
	}
	//取出栈底元素
	//依次为1，2，3，4，5
	int i = getAndRemoveLastElement(stack);
	//递归调用，使得栈空
	reverse(stack);
	//压入栈底元素i
	//因此5，4，3，2，1被压入
	stack.push(i);
}

//取得栈底元素，并且其余元素与原始状态相同
public static int getAndRemoveLastElement(Stack<Integer> stack) {
	//result取得栈顶
	int result = stack.pop();
	if (stack.isEmpty()) {
		//栈空返回栈顶，那么最后应该返回1
		return result;
	} else {
		//得到栈空的返回值1
		int last = getAndRemoveLastElement(stack);
		//此时栈是空的，压入上一次的res
		//依次为2，3，4，5
		stack.push(result);
		//返回last即1
		//由此可见每次返回的都是last1
		return last;
	}
}

public static void main(String[] args) {
	Stack<Integer> test = new Stack<Integer>();
	test.push(1);
	test.push(2);
	test.push(3);
	test.push(4);
	test.push(5);
	reverse(test);
	while (!test.isEmpty()) {
		System.out.println(test.pop());
	}

}