面试题:递归颠倒栈 与栈排序 - youxin - 博客园

面试题:递归颠倒栈 与栈排序 - youxin - 博客园
题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。
http://zhedahht.blog.163.com/blog/static/25411174200943182411790/

我们把栈{1, 2, 3, 4, 5}看成由两部分组成：栈顶元素1和剩下的部分{2, 3, 4, 5}。如果我们能把{2, 3, 4, 5}颠倒过来，变成{5, 4, 3, 2}，然后在把原来的栈顶元素1放到底部，那么就整个栈就颠倒过来了，变成{5, 4, 3, 2, 1}。（思路类似hanoi问题）

我们需要考虑的另外一件事情是如何把一个元素e放到一个栈的底部，也就是如何实现AddToStackBottom。这件事情不难，只需要把栈里原有的元素逐一pop出来。当栈为空的时候，push元素e进栈，此时它就位于栈的底部了。然后再把栈里原有的元素按照pop相反的顺序逐一push进栈。

注意到我们在push元素e之前，我们已经把栈里原有的所有元素都pop出来了，我们需要把它们保存起来，以便之后能把他们再push回去。我们当然可以开辟一个数组来做，但这没有必要。由于我们可以用递归来做这件事情，而递归本身就是一个栈结构。我们可以用递归的栈来保存这些元素。

// Add an element to the bottom of a stack:

template<typename T> void AddToStackBottom(std::stack<T>& stack, T t)

{

    if(stack.empty())

    {

        stack.push(t);

    }

    else

    {

        T top = stack.top();

        stack.pop();

        AddToStackBottom(stack, t);

        stack.push(top);

    }

}

http://bylijinnan.iteye.com/blog/1447035

1.      * Q 66.颠倒栈。 
2.      * 题目：用递归颠倒一个栈。例如输入栈{1,2,3,4,5}，1在栈顶。 
3.      * 颠倒之后的栈为{5,4,3,2,1}，5处在栈顶。 
4.      *1. Pop the top element 
5.      *2. Reverse the remaining stack 
6.      *3. Add the top element to the bottom of the remaining stack 
7.      */  

1.     public void reverseStack(Stack<Integer> stack){  
2.         if(!stack.empty()){  
3.             Integer top=stack.pop();  
4.             reverseStack(stack);  
5.             addToBottom(stack,top);  
6.         }  
7.     }  
8.     public void addToBottom(Stack<Integer> stack,Integer ele){  
9.         if(stack.empty()){  
10.             stack.push(ele);  
11.         }else{  
12.             Integer top=stack.pop();  
13.             addToBottom(stack,ele);//important  
14.             stack.push(top);  
15.         }  
16.     }

Read full article from 面试题:递归颠倒栈 与栈排序 - youxin - 博客园