程序员面试题精选100题（39）-颠倒栈[数据结构] (2)

{

    if(!stack.empty())

    {

        T top = stack.top();

        stack.pop();

        ReverseStack(stack);

        AddToStackBottom(stack, top);

    }

}

我们需要考虑的另外一件事情是如何把一个元素e放到一个栈的底部，也就是如何实现AddToStackBottom。这件事情不难，只需要把栈里原有的元素逐一pop出来。当栈为空的时候，push元素e进栈，此时它就位于栈的底部了。然后再把栈里原有的元素按照pop相反的顺序逐一push进栈。

注意到我们在push元素e之前，我们已经把栈里原有的所有元素都pop出来了，我们需要把它们保存起来，以便之后能把他们再push回去。我们当然可以开辟一个数组来做，但这没有必要。由于我们可以用递归来做这件事情，而递归本身就是一个栈结构。我们可以用递归的栈来保存这些元素。

基于如上分析，我们可以写出AddToStackBottom的代码：

// Add an element to the bottom of a stack:

template<typename T> void AddToStackBottom(std::stack<T>& stack, T t)

{

    if(stack.empty())

    {

        stack.push(t);

    }