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

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();
	}
}