使用递归反转一个栈

小咪咪 2022-08-04 09:19 144阅读 0赞

反转递归栈的内容

使用递归，一定要明白递归结束的条件，假如栈中只有一个元素或者没有元素，那么这个栈就不用递归。那么我们将栈顶元素取出来，将余下的元素进行反转，那么将取出的元素放到栈的底部即可。

对于将一个元素放到底部，又是一个递归的调用，如果栈为空，那么直接将元素存放到栈的底部即可，如果栈中有元素，那么取出栈内的元素，将原来的元素再次调用函数存放到栈底，然后将取出的元素压入栈即可。

感觉这个例子是利用递归的典范

#include <iostream>  
        #include <stack>  
        #include <vector>  
        using namespace std;  
        /* 
        使用递归来反转一个栈   
        */   
          
        void Push_Bottom(stack<int>& st,int value)  
        {  
            int tmp;  
            if(st.size()==0)  
                st.push(value);  
            else  
            {  
                tmp = st.top();  
                st.pop();  
                Push_Bottom(st,value);  
                st.push(tmp);  
            }  
              
        }  
        void Reverse_st(stack<int>& st)  
        {  
            int tmp;  
            if(st.size()<=1)  
                return;  
            else  
            {  
                tmp = st.top();  
                st.pop();  
                Reverse_st(st);  
                Push_Bottom(st,tmp);      
            }     
              
              
        }  
        int main()  
        {  
            stack<int> st;  
            int i;  
            int tmp;  
            for(i=0;i<5;i++)  
                st.push(i);  
              
            Reverse_st(st);  
        //  Push_Bottom(st,5);  
            while(!st.empty())  
            {  
                tmp = st.top();  
                cout<<tmp<<endl;  
                st.pop();  
            }     
            return 0;  
        }