一个栈依次压入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]
思想：把栈的逆序分为两步，第一步，将最上面的数出栈保存，然后将下面的栈逆序（这里用到递归）；第二步，将原先最上面的数插到最底层（我用一个函数实现）。
class ReverseStack {
public:
vector
stack, int top) {
if(top==1)//只有一个数的时候直接返回
return stack;
int temp;
temp=stack.back();
stack.pop_back();//最上面的数出栈
stack=reverseStackRecursively(stack,top-1);//递归调用
stack=insertToBottom(stack,temp); //用一个函数实现将一个数插入到最底层
return stack;
}
vector
num)//将一个数插入到栈的最底层的函数
{
if(stack.size()==0)//栈空
{
stack.push_back(num);
return stack;
}
int top=stack.back();
stack.pop_back();//将最上面的数出栈保存
stack=insertToBottom(stack,num);//把数插入到最底层
stack.push_back(top);//再把原先的最上面的数入栈
return stack;
}
};
