首页 > 试题广场 >

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

[编程题]用递归函数和栈操作逆序栈
  • 热度指数：8100 时间限制：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)
Java
无可救药的菜鸡头像 无可救药的菜鸡 
public int[] reverseStackRecursively(int[] stack, int top) {
    if(top <= stack.length / 2) {
        return stack;
    }
    int x = top;
    int[] newStack = reverseStackRecursively(stack, --x);
    int index = newStack.length - top;
    int temp = 0;
    temp = newStack[index];
    newStack[index] = newStack[top-1];
    stack[top-1] = temp;
    return newStack;
}

发表于 2020-09-12 20:44:57 回复(0)
Java
八十寸的二八头像 八十寸的二八
public class ReverseStack {
    // top:stack的size
    public int[] reverseStackRecursively(int[] stack, int top) {
        if(top == 0) return stack;
        int last = getLastAndRemove(stack, top--);
        stack = reverseStackRecursively(stack, top);
        stack[top] = last;
        return stack;
    }
    
    // 获取并移除栈底元素
    private int getLastAndRemove(int[] stack, int top) {
        int result = stack[top - 1];
        top--;
        if(top == 0) return result;
        int last = getLastAndRemove(stack, top--);
        stack[top] = result;
        return last;
    }
}
发表于 2018-03-03 00:45:27 回复(0)
Java
Holiday_12138头像 Holiday_12138 
import java.util.*;

public class ReverseStack {
    public int getBottom(int[] stack,int top){
         if(top==1)
             return stack[top-1];
        else{
            int tmp=stack[top-1];
            top--;
            int bottom=getBottom(stack,top);
            stack[top-1]=tmp;
            top++;
            return bottom;
        }
    }
    public int[] reverseStackRecursively(int[] stack, int top) {
       	if(top<1){
           	return stack;
       	}
        else{
            int bottom=getBottom(stack,top--);
            stack=reverseStackRecursively(stack, top);
            stack[top++]=bottom;
            return stack;
        }
    }
}

发表于 2017-04-01 15:05:59 回复(0)
Java
swtywang头像 swtywang
import java.util.*;
public class ReverseStack {
public int[] reverseStackRecursively(int[] stack, int top) {
if (top==stack.length/2)
return stack;
swap(stack,top-1,stack.length-top);
top--;
return reverseStackRecursively(stack, top);
}
public static void swap(int[] stack,int i, int j ){
int temp = stack[i];
stack[i]=stack[j];
stack[j]=temp;
}
}
编辑于 2016-07-11 22:37:42 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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