学步园

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

/*
66.颠倒栈。
题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

每一次试图颠倒一个栈的时候，现在栈顶元素pop出来，再颠倒剩下的元素组成的栈，
最后把之前的栈顶元素放到剩下元素组成的栈的底部。
递归结束的条件是剩下的栈已经空了
*/
#include <iostream>  
#include <stack>  
using namespace std;  
  
void PushToButtom(stack<int>*s,int ele)  
{  
    if(s->empty()) //栈是空的 直接放入 
    {  
        s->push(ele);  
        return;  
    }  
    else  
    {  
        int tmp=s->top();  //不是空的，依次出栈 
        s->pop();  
        PushToButtom(s,ele); //为空，ele放入栈底 
        s->push(tmp);  		//再依次进栈 
    }  
}  
  
void reverse(stack<int> *s)  
{  
    int top;
    if(!s->empty())
    {
    	top=s->top();  
    	s->pop();  //每次取出栈顶元素 
    	reverse(s);  //颠倒栈剩下的元素 
   	 	PushToButtom(s,top);  //把栈顶元素放入底部 
    }
}  
  
int main()  
{  
    stack<int> *s=new stack<int>;  
    for(int i=1;i<10;i++)//1 2 ...9 进栈 ，栈顶9 栈底1，出栈为9 8 7.... 
		s->push(i);
		
    reverse(s);  
    
    while(!s->empty()) //颠倒后9 8 7...1，栈顶1 栈底9，出栈为1 2 3.... 
    {  
        cout <<s->top()<< " ";  
        s->pop();  
    }  
  
}