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

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

一、题目

将一个栈用递归实现逆序，即：插入栈比如是：1、2、3、4、5。栈中存储从底到顶是1、2、3、4、5。逆序后，希望存储的从底到顶是5、4、3、2、1。只能使用递归

二、思路

递归就是使用了操作系统为我们程序提供的栈空间，这块空间也是栈结构。也就是说我们需要操作系统的栈为我们存储什么东西。我们标记操作系统的栈为 A；业务栈为 B。

在这个题目中，我们需要栈 A 为我们保存栈 B 每一个元素。因此，

• 我们先做第一步，拿到栈 B 的最底的元素，并让他出栈 B。这个过程也利用操作系统栈来保存栈 B 从底到顶的元素。
• 依次循环第一步操作，并把每次操作得到的元素保存起来。结束后，再插入回栈 B 即可。这个保存的动作需要操作系统栈。

三、code

#include <stack>
#include <iostream>
#include <vector>
#include <algorithm>

class Solution {
public:
    void push(std::vector<int> vec) {
        std::for_each(vec.begin(), vec.end(), [&](int val) {
            st.push(val);
        });
    }
    void print() {
        std::stack<int> tmp_st;
        while (!st.empty()) {
            tmp_st.push(st.top());
            st.pop();
        }
        while (!tmp_st.empty()) {
            int val = tmp_st.top();
            std::cout << val << " ";
            st.push(val);
            tmp_st.pop();
        }
        std::cout << std::endl;
    }
    void reverse_stack() {
        if (st.empty()) {
            return;
        }
        // 比如插入业务栈是 1、2、3、4、5，业务栈元素从底到顶为 1、2、3、4、5
        // 这里获取到的元素的顺序为 1、2、3、4、5
        int last = get_stack_bottom_elem();
        reverse_stack();
        // 当业务栈为空，最后一次获取的元素即为 5。则插入顺序变为 5、4、3、2、1。即可实现逆序
        st.push(last);
    }

private:
    //  获取栈底元素并出栈
    int get_stack_bottom_elem() {
        // 这个 result 就是通过操作系统栈来保存业务栈的每一个元素
        // 只不过仅仅返回业务栈最底的元素
        int result = st.top();
        st.pop();
        if (st.empty()) {
            return result;
        } else {
            // last 获取到业务栈底的元素，保存起来，依次返回出去，直到递归结束
            int last = get_stack_bottom_elem();
            // 重新将业务栈的元素插回去
            st.push(result);
            return last;
        }
    }

private:
    std::stack<int> st;
};

int main() {
    Solution s;
    s.push({1, 2, 3, 4, 5});
    s.print();
    s.reverse_stack();
    s.print();
}