仅用递归函数和栈操作逆序一个栈

朱雀 2022-07-24 09:20 100阅读 0赞

## 仅用递归函数和栈操作逆序一个栈 – C++ ##

--------------------

题目：  
一个栈依次压入1、2、3、4、5，那么栈顶到栈底分别为：5、4、3、2、1。  
将这个栈逆置后栈顶到栈底分别为1、2、3、4、5。  
用递归函数来实现，不能用其他数据结构。

--------------------

## 解题思路及代码 ##

1、递归函数一：将栈的栈底元素一个个返回并移除。  
2、递归函数二：逆序栈，调用递归函数一实现。

C++实现：

class Solution
    {
    public:
        //递归函数一
        static int getAndRemoveStackLastElem(stack<int>& s)
        {
            int result = s.top();
            s.pop();
            if (s.empty())
                return result;
            else
            {
                int last = getAndRemoveStackLastElem(s);
                s.push(result);
                return last;
            }
        }
    
        //递归函数二
        static void reverseStack(stack<int>& s)
        {
            if (s.empty())
                return;
    
            int i = getAndRemoveStackLastElem(s);
            reverseStack(s);
            s.push(i);
        }
    };

--------------------

程序测试用例：

#include <iostream>
    #include <stack>
    using namespace std;
    
    class Solution
    {
    public:
        static int getAndRemoveStackLastElem(stack<int>& s)
        {
            int result = s.top();
            s.pop();
            if (s.empty())
                return result;
            else
            {
                int last = getAndRemoveStackLastElem(s);
                s.push(result);
                return last;
            }
        }
    
        static void reverseStack(stack<int>& s)
        {
            if (s.empty())
                return;
    
            int i = getAndRemoveStackLastElem(s);
            reverseStack(s);
            s.push(i);
        }
    };
    //打印栈
    void show(stack<int> s)
    {
        while (!s.empty())
        {
            cout << s.top() << " ";
            s.pop();
        }
        cout << endl;
    }
    
    int main()
    {
        stack<int> s;
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        s.push(5);
        s.push(6);
        cout << "Before reverse: " << endl;
        show(s);
    
        cout << "After reverse: " << endl;
        Solution::reverseStack(s);
        show(s);
    
        system("pause");
    }

运行结果：

Before reverse:
    6 5 4 3 2 1
    After reverse:
    1 2 3 4 5 6
    请按任意键继续. . .