java-66-用递归颠倒一个栈。例如输入栈{1,2,3,4,5}，1在栈顶。颠倒之后的栈为{5,4,3,2,1}，5处在栈顶

import java.util.Stack;

public class ReverseStackRecursive {

	/**
	 * Q 66.颠倒栈。
	 * 题目：用递归颠倒一个栈。例如输入栈{1,2,3,4,5}，1在栈顶。
	 * 颠倒之后的栈为{5,4,3,2,1}，5处在栈顶。
	 *1. Pop the top element
	 *2. Reverse the remaining stack
	 *3. Add the top element to the bottom of the remaining stack
	 */
	public static void main(String[] args) {
		ReverseStackRecursive r=new ReverseStackRecursive();
		Stack<Integer> stack=new Stack<Integer>();
		for(int i=0;i<10;i++){
			stack.add(i);
		}
		r.printStack(stack);
		r.reverseStack(stack);
		r.printStack(stack);
	}

	public void reverseStack(Stack<Integer> stack){
		if(!stack.empty()){
			Integer top=stack.pop();
			reverseStack(stack);
			addToBottom(stack,top);
		}
	}
	public void addToBottom(Stack<Integer> stack,Integer ele){
		if(stack.empty()){
			stack.push(ele);
		}else{
			Integer top=stack.pop();
			addToBottom(stack,ele);//important
			stack.push(top);
		}
	}
	public void printStack(Stack<Integer> stack){
		/*
		while(!stack.empty()){
			System.out.print(stack.pop()+",");
		}
		*/
		//we don't remove the elements in the stack.
		for(Integer x:stack){
			System.out.print(x+",");
		}
		System.out.println();
	}
}

评论

4 楼 bylijinnan 2012-10-13  

neyshule 写道

这样做貌似还不如直接把栈倒到一个queue或是list里面再往回填。。空间复杂度都是n啊，这个算法每次都要开辟一个integer，而且递归还更废不是吗？

从效率上来说的确是那样的

但这道题目是考察递归吧 题目明确规定是 用递归颠倒一个栈

3 楼 neyshule 2012-10-13  

neyshule 写道

Integer top=stack.pop(); 
addToBottom(stack,ele);//important 
stack.push(top);
代码都不对吧，你想一下别扭吗？ 

不好意思是对的，看错了。。

2 楼 neyshule 2012-10-13  

Integer top=stack.pop(); 
addToBottom(stack,ele);//important 
stack.push(top);
代码都不对吧，你想一下别扭吗？ 

1 楼 neyshule 2012-10-13  

这样做貌似还不如直接把栈倒到一个queue或是list里面再往回填。。空间复杂度都是n啊，这个算法每次都要开辟一个integer，而且递归还更废不是吗？