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

问题

链接：https://www.nowcoder.com/questionTerminal/ba7d7f5d1edf4d1690d66e12e951f6ea
题目来源：牛客网

一个栈依次压入1,2,3,4,5 那么从栈顶到栈底分别为5,4,3,2,1。 将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，但是只能用递归函数来实现，而不能用另外的数据结构。

给定一个栈Stack以及栈的大小top，请返回逆序后的栈。

测试样例：

[1,2,3,4,5],5

返回：

[5,4,3,2,1]

分析

递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

通过递归实现栈的逆序，相当于使用函数调用自身完成栈的逆序操作。
因为栈是先进后出，因此先出旧栈的元素要先入新栈，所有旧元素操作完成后，新栈就是原栈的逆序。

代码

#include <stack>
#include <iostream>
 
 
/**
 * 递归处理栈中的元素，并存储结果。
 *
 * @param s 输入的整数栈，作为递归处理的对象。
 * @param s_top 当前栈顶元素的值，用于递归基准条件或计算。
 * @param ret 输出栈，用于存储递归处理后的结果。
 */
void recursion_stack(std::stack<int> &s, int s_top, std::stack<int> &ret) {
    ret.push(s_top);
    s.pop();
 
    if (!s.empty()) {
        return recursion_stack(s, s.top(), ret);
    }
}
 
 
#ifdef _GTEST
 
#include "gtest/gtest.h"
 
TEST(test_recursion_stack, recursion)
{
    std::stack<int> s1, s2, s3;
    std::stack<int> r;
 
    for (size_t i = 1; i <= 5; ++i) {
        s1.push(i);
        s2.push(i);
    }
    for (; !s2.empty(); s2.pop()) {
        s3.push(s2.top());
    }
 
    recursion_stack(s1, s1.top(), r);
 
    for (; !r.empty(); ) {
        EXPECT_EQ(s3.top(), r.top());
        s3.pop();
        r.pop();
    }
}
#endif//_GTEST
 

Build:

g++ -o sr.bin stack_recursion.cpp -g -D_GTEST -lgtest_main -lgtest -I/usr/src/gtest/include -L/usr/lib/x86_64-linux-gnu/

Run:

 ❯ ./sr.bin
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from test_recursion_stack
[ RUN      ] test_recursion_stack.recursion
[       OK ] test_recursion_stack.recursion (0 ms)
[----------] 1 test from test_recursion_stack (0 ms total)
 
[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (0 ms total)
[  PASSED  ] 1 test.

*****