{
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);
}