首页 > 试题广场 >

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

[编程题]用递归函数和栈操作逆序栈
  • 热度指数:8003 时间限制: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]
推荐
思想:把栈的逆序分为两步,第一步,将最上面的数出栈保存,然后将下面的栈逆序(这里用到递归);第二步,将原先最上面的数插到最底层(我用一个函数实现)。
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)
return stack[::-1]
发表于 2017-09-12 11:59:01 回复(3)
注意不能使用额外的数据结构!
其实类似深度优先搜索。
C++代码如下:
int level = 0;
    
    vector<int> reverseStackRecursively(vector<int> stack, int top) {
        if(top > 0){
            int val = stack[top - 1];
            ++level;
            stack = reverseStackRecursively(stack, top - 1);
            --level;
            stack[level] = val;
        }
        
        return stack;
    }

编辑于 2016-05-02 21:50:36 回复(2)
/*
Coding Interview Guide:用递归函数和栈操作逆序栈
题目大意:
一个栈依次压入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]

解题思路:
用一个递归函数,每次获取栈的最底部的元素并移除
*/

#include <iostream>
#include <vector>
using namespace std;

class ReverseStack {
public:
    vector<int> reverseStackRecursively(vector<int> stack, int top)
    {
        vector<int> ret;
        if (stack.empty())
            return ret;


        int k = getLastElem(stack);//获取最底部元素
        stack = reverseStackRecursively(stack, top - 1);//递归调用
        stack.push_back(k);//压入栈

        return stack;
    }

    //获取stack最底部的元素并移除
    int getLastElem(vector<int> &stack)
    {
        int top = stack.back();
        stack.pop_back();
        if (stack.empty())
            return top;
        else
        {
            int last = getLastElem(stack);
            stack.push_back(top);
            return last;
        }
    }
};

int main()
{
    vector<int> v{ 1,2,3,4,5 };
    ReverseStack obj;
    vector<int> ret = obj.reverseStackRecursively(v, v.size());
    for (auto num : ret)
        cout << num << " ";
    cout << endl;
}
发表于 2017-06-14 16:02:11 回复(0)
//大家好,我是yishuihan,下面的思路清晰,可以参考;
//当某一个元素放入栈底部
void Push_Bottom(stack<int>& st,int value)  
{  
    int tmp;  
    //如果栈为空,那么直接将当前元素压入栈 
    if(st.size()==0)  
        st.push(value);  
    else  //如果栈中有元素,那么取出其中的元素,然后再将元素压入 
    {  
        tmp = st.top();  
        st.pop();  
        Push_Bottom(st,value);  
        st.push(tmp);  
    }  
}  

/*
翻转栈 
*/ 
void Reverse_st(stack<int>& st)  
{  
    int tmp;  
    if(st.size()<=1)  
        return;  
    else  
    {  
    	//取出栈顶元素 
        tmp = st.top();  
        st.pop();  
        //递归调用,翻转剩余的元素 
        Reverse_st(st);  
        //将取出的元素放入栈底部 
        Push_Bottom(st,tmp);      
    }             
} 

编辑于 2016-08-08 20:50:26 回复(0)
通过递归将数组中的数据压入栈,再取出来倒序存储。
import java.util.*;

public class ReverseStack {
    int i = 0;
    public int[] reverseStackRecursively(int[] stack, int top) {
        // write code here
        if(top>0)
        {

        int a = stack[top-1];
        i++;
        stack = reverseStackRecursively(stack,top-1);
        i--;
        stack[i] = a;
        }
        return stack;
    }
}
发表于 2016-04-14 15:27:10 回复(5)
import java.util.*;
说实话,这个题最开始没写到,应为自己总是想反转应该是全部反转,
然后看到大佬们的答案后,瞬间豁然开朗, 原来反转,如果在原数组里面,
直接从中间开始,向俩边交换就行了,还省空间。很棒!
并且自己对递归又加深了认识。!应为我在刷递归专题。若果有小伙伴,一起刷题的,可以加关注哦。讨论
public class ReverseStack {
    
    public int[] reverseStackRecursively(int[] stack, int top) {
        reve(stack,0);
        return stack;
    }
    public void reve(int[] arr, int n){
        if(n>=arr.length/2)
            return;
        reve(arr,n+1);
        int temp = arr [n];
        arr[n] = arr[arr.length-n-1];
        arr[arr.length-n-1] = temp;
        return;
    }
}

发表于 2017-03-12 16:25:38 回复(3)
import java.util.*;

public class ReverseStack {
    public int[] reverseStackRecursively(int[] stack, int top) {
        // write code here
        int[] result=new int[top];
        for(int i=top-1,j=0;i>=0;i--,j++){
            result[j]=stack[i];
        }
        return result;
    }
} 

发表于 2018-10-16 11:09:02 回复(0)

//总共用了四行代码
//每次交换两个位置的值,比如top = 5;那么第一次交换的就是下标为0和下标为top-1的值
//第二次就是交换下标为1和下标为(top - 1)- 1的值
//因为stack的size是不会变的,变的是传的top
//因此下标为0可以用stack.size-top来表示,依次类推,因为每进入一个递归,top都会--

//终止的条件是stack.size-top的值大于(偶数个)或等于(奇数个)top - 1的值了

vector<int> reverseStackRecursively(vector<int> stack, int top) {
    if (stack.size() - top >= top - 1 )
        return stack;
    swap(stack[stack.size() - top], stack[top - 1]);
    return reverseStackRecursively(stack,--top);
}

编辑于 2018-06-21 17:49:18 回复(0)
class ReverseStack:
    def reverseStackRecursively(self, stack, top):
        # write code here
        if top == 1:
            return stack
        if top == 2:
            return stack[::-1]
        stack[0], stack[top-1] = stack[top-1], stack[0]
        return [stack[0]] + self.reverseStackRecursively(stack[1:top-1],top-2) + [stack[top-1]]
掐头去尾,两者交换,然后递归
发表于 2018-06-04 10:02:00 回复(0)
class ReverseStack {
public:
    vector<int> reverseStackRecursively(vector<int> stack,int top) {
        top--;
        if(top==-1||top==0) return stack;
        reverseStack(stack,top);
        return stack;
    }
    int getAndRemoveLastElement(vector<int> &stack,int &top){
        int res=stack[top--];
        if(top==-1) return res;
        int last=getAndRemoveLastElement(stack,top);
        stack[++top]=res;
        return last;
    }
    void reverseStack(vector<int> &stack,int &top){
        if(top==-1) return;
        int lastElement=getAndRemoveLastElement(stack,top);
        reverseStack(stack,top);
        stack[++top]=lastElement;
    }
};

发表于 2017-12-03 00:34:22 回复(0)
import java.util.*;

public class ReverseStack {
    public int[] reverseStackRecursively(int[] stack, int top) {
        // write code here
        if (top == 0) return null;
        return reverse(stack, 0, top - 1);
    }
    
    private int[] reverse(int[] stack, int begin, int end) {
        if (begin >= end) {
            return stack;
        }
        int tmp = stack[begin];
        stack[begin] = stack[end];
        stack[end] = tmp;
        return reverse(stack, begin + 1, end - 1);
    }
}

发表于 2017-09-13 23:10:41 回复(0)
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)
import java.util.*;

public class ReverseStack {
    public int[] reverseStackRecursively(int[] stack, int top) {
        recursion(stack,0);
        return stack;
    }
    void recursion(int[] stack, int i){
        if(i>=stack.length/2)
            return;
        recursion(stack,i+1);
        int temp = stack[stack.length-i-1];
        stack[stack.length-i-1] = stack[i];
        stack[i] = temp;
        return;
    }
}

发表于 2016-12-09 00:08:13 回复(0)
class ReverseStack {
public:
    int getAndRemoveLast(vector<int>& stack){
        int front=stack[stack.size()-1];
        stack.pop_back();
        if(stack.empty()){
            return front;
        }else{
        	int last=getAndRemoveLast(stack);
            stack.push_back(front);
            return last;
        }
    }
    void reverseStack(vector<int>& stack){
        if(stack.size()<2)
            return;
        else{
            int last=getAndRemoveLast(stack);
            reverseStack(stack);
            stack.push_back(last);
        }
    }
    vector<int> reverseStackRecursively(vector<int> stack, int top) {
          reverseStack(stack);
          return stack;
    }
};

发表于 2016-09-09 10:29:47 回复(0)

//双重递归
class ReverseStack {
public:    
     vector<int> PushStack(vector<int> stack, int toptmp)
    {
        if(stack.size()==0)
        {
            stack.push_back(toptmp);
        }
        else
        {
            int tmp=stack.back();
            stack.pop_back();
            stack=PushStack(stack, toptmp);
            stack.push_back(tmp);
        }       
        return stack;
    }
   
    vector<int> reverseStackRecursively(vector<int> stack, int top) 
    {
        if(top==1)return stack;
        int toptmp= stack.back();//取出栈顶元素
        stack.pop_back();//删除栈顶元素
        stack=reverseStackRecursively(stack, top-1);//栈逆序
        stack=PushStack(stack,toptmp);//将栈顶元素压入栈底  
        return stack;
              // write code here
    }   
};
发表于 2016-09-08 18:02:32 回复(0)
采用Decrease and Conquer 的思想,将 第N个元素插入N-1(已经完成逆序)的底部。这是第一步递归,第二次如何将N元素插入底部,采用递归的栈保存递归数据,这是第二次递归。

class ReverseStack
{
    public int[] reverseStackRecursively(int[] stack, int top)
    {
       Reverse(stack,top-1); 
        return stack;
    }
    private void Reverse(int[] stack,int top){
        if(top==0)
            return;
        else{
            int current=stack[top];
            top=top-1;
            Reverse(stack,top);
            AnotherReverse(stack,ref top,current);
            
        }
    }
    private void AnotherReverse(int[] stack,ref int top,int value){
        if(top==0){
            int backup=stack[top];
            stack[top]=value;
            top++;
            stack[top]=backup;
        }else{
            int current=stack[top];
            top--;
            AnotherReverse(stack,ref top,value);
            top++;
            stack[top]=current;
        }
    }
}

发表于 2016-07-27 20:42:59 回复(0)
//如果不用递归,那么就是循环的将左右两边对称的数进行交换,例如对于数组{1,2,3,4,5},将1和5,2和4进行交换即可。用递归的话,就是根据第二个参数来交换。
public class ReverseStack {
	public static void main(String args[]) {
		int[] arr = new ReverseStack().reverseStackRecursively(new int[] { 1, 2, 3, 4, 5}, 5);
		for (int x : arr)
			System.out.print(x + " ");
	}

	public int[] reverseStackRecursively(int[] stack, int top) {
		int temp = stack[stack.length - top];
		stack[stack.length - top] = stack[top - 1];
		stack[top - 1] = temp;
		for (int i = 1; i < top / 2; i++) {
			reverseStackRecursively(stack, top - i);
		}
		return stack;
	}

}

编辑于 2016-05-12 21:33:01 回复(0)
class ReverseStack {
public:
    int k = 0;
    vector<int> reverseStackRecursively(vector<int> stack, int top) {         if(top>0)
        {
            int x = stack[top-1];
            k++;
            stack = reverseStackRecursively(stack, top-1);
            k--;
            stack[k] = x;         }         return stack;
    }
};

发表于 2017-10-23 09:04:59 回复(0)
听了第三季左老师的课,按做老师的思路实现了一遍:
1. 实现getAndRemoveLastElement用来移除stack的栈底元素并返回(用数组实现比用stack简单多了,stack还要递归)
2. 递归调用主函数,每次从栈中抽出底部元素,直到把栈抽空,再回溯反压入栈

import java.util.*;

public class ReverseStack {
    
    public int[] reverseStackRecursively(int[] stack, int top) {
        // write code here
        int size = top;
        if(size == 0){    // 已把栈抽空,开始回溯(反压)
            return stack;
        }
        int i = getAndRemoveLastElement(stack, size);
        size--;
        reverseStackRecursively(stack, size);
        stack[size] = i;  // 把抽出的元素反压入栈
        return stack;
    }
    
    /**
     * 移除stack的栈底元素,其他元素不变
     *
     * @param stack
     * @param size
     * @return 返回所移除的栈底元素
     */
    public int getAndRemoveLastElement(int[] stack, int size){
        int last = stack[0];
        for(int i = 0; i < size - 1; i++){
            stack[i] = stack[i + 1];
        }
        return last;
    }
}
编辑于 2017-07-27 10:44:46 回复(1)
/**
 * 思路:给你的参数是栈的大小top,每一次压栈,top--,向下标0移动,这时应该增加一个计数器,从0开始,每压一个栈就+1,这样与对应的元素进行颠倒存储在栈中
 * 这里利用了每一个栈会保存当前栈的局部变量的特点。
 */
importjava.util.*; 
publicclassReverseStack {
    publicint[] reverseStackRecursively(int[] stack,inttop) {
         inti = -1;
        int[] result = reverseStackRecursively(stack, top, i);    // 计数器i,从0开始递增,top从stack的长度开始递减
        returnresult;
    }
     
     public int[] reverseStackRecursively(int[] stack,inttop,inti){
 
        if(top >0){
            inttemp = stack[top -1];
            i = i +1;
            reverseStackRecursively(stack,top -1,i);
            stack[i] = temp;
        }
         returnstack;
     }
}
 
发表于 2015-09-10 16:48:35 回复(0)

问题信息

难度:
81条回答 46676浏览

热门推荐

通过挑战的用户

查看代码