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

牛客网上讲的一道题，学会这道题将对递归有更进一步的理解。
（视频链接： http://www.nowcoder.com/discuss/1944 ）

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

下面是C++代码：
template <typename T>
const T getAndRemoveLastElem(stack<T>& s)//移除并返回栈底元素
{
    T rlt = s.top();
    s.pop();
    if (s.empty())  return rlt;
    else
    {
        T last = getAndRemoveLastElem(s);
        s.push(rlt);
        return last;
    }
}

template <typename T>
void reverse_stack(stack<T>& s)
{
    if (s.empty())
        return;
    T tmp = getAndRemoveLastElem(s);

    reverse_stack(s);
    s.push(tmp);
}


原创 转载 翻译 都不是。。。。。

版权声明：本文为defineYouMyHeart原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。