首页 > 试题广场 >

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

[编程题]用递归函数和栈操作逆序栈

热度指数：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

思想：把栈的逆序分为两步，第一步，将最上面的数出栈保存，然后将下面的栈逆序（这里用到递归）；第二步，将原先最上面的数插到最底层（我用一个函数实现）。

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)

Python

华科平凡

return stack[::-1]

发表于 2017-09-12 11:59:01 回复(3)

LEarBB

注意不能使用额外的数据结构！

其实类似深度优先搜索。

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)

C/C++

yanke

/*
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)

dragonlogin

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)

kestars

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)

pigff201711160008193

//总共用了四行代码
//每次交换两个位置的值，比如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)

BIG_DAN

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)

Java

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)

...王嘉廉睿

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)

fight灬奋斗

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)

Gaufung

采用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)

C/C++

nbgao

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条回答 140收藏 47474浏览

通过挑战的用户

查看代码

曹宝龙

2023-02-09 09:51:42
destiny...

2022-12-10 16:35:25
TankWitch

2022-11-26 20:22:52
求-offer

2022-10-26 23:55:18
天天摸鱼的秋田...

2022-10-12 23:44:10

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

问题信息

热门推荐

通过挑战的用户

相关试题