首页 > 试题广场 >

用递归函数和栈操作逆序栈

[编程题]用递归函数和栈操作逆序栈
  • 热度指数：8045 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

一个栈依次压入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]
算法知识视频讲解
添加回答
推荐
kevinLee523头像 kevinLee523
思想：把栈的逆序分为两步，第一步，将最上面的数出栈保存，然后将下面的栈逆序（这里用到递归）；第二步，将原先最上面的数插到最底层（我用一个函数实现）。
class ReverseStack {
public:
     vector<int> reverseStackRecursively(vector<int> 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<int> insertToBottom(vector<int> stack,int 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;
        
    }
};
编辑于 2016-03-25 11:03:25 回复(5)
提交观点

问题信息

栈 递归
来自：常见面试题精讲（四）
难度：
0条回答 47464浏览

热门推荐

通过挑战的用户

查看代码

相关试题

用递归函数和栈操作逆序栈

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号