程序员代码面试指南 1.3：用递归函数和栈逆序一个栈

1、思路

递归地每次取得栈底元素，当达到最后一层递归时取得的就是栈顶元素了，再利用递归返回，将栈顶元素push入栈底即可。

2、实现

需要构造两个递归函数来实现栈的逆序：

• getAndRemoveLastElement()方法能够递归把栈弹出，取得并移除栈底元素后，再恢复栈；
• reverse()方法用来递归取得栈底元素，

3、代码

#include <iostream>
#include <stack>

using namespace std;

int getAndRemoveLastElement(stack<int>& stk)        //移除并返回栈底元素
{
    int num = stk.top();    //先取得当前栈顶元素
    stk.pop();

    if (stk.empty())        //栈空说明已经到栈底了，直接返回当前栈底元素
    {
        return num;
    }
    else                    //还没到栈底，继续往下走
    {
        int last = getAndRemoveLastElement(stk);    
        stk.push(num);
        return last;        //last就是栈底元素，一层一层传上来，作为最后的返回值
    }
}

void reverse(stack<int>& stk)
{
    if (stk.empty()) return ;

    int i = getAndRemoveLastElement(stk);       //取得栈底元素
    reverse(stk);                               //最后一层递归时取得栈顶元素
    stk.push(i);                                //将栈顶元素push入栈底
}

int main()
{
    stack<int> stk;
    int n;
    cin >> n;

    while (n -- )            //输入栈元素
    {
        int num;
        cin >> num;

        stk.push(num);
    }

    reverse(stk);

    while (!stk.empty())    //输出栈元素
    {
        cout << stk.top() << " ";
        stk.pop();
    }

    return 0;
}