首页 > 编程学习 > 用递归函数和栈操作逆序栈

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

发布时间:2022/10/1 7:48:09

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

作者:Grey

原文地址:

博客园:用递归函数和栈操作逆序栈

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

题目描述

请设计一个算法实现逆序栈的操作,但是只能用递归函数来实现,而不能用另外的数据结构。给定一个栈Stack以及栈的大小top,请返回逆序后的栈。

题目链接:牛客-用递归函数和栈操作逆序栈

首先,如果我们可以用递归函数实现这样的功能:获取一个栈的栈底元素并返回栈底元素,然后把栈底元素删除,并把剩余元素压下来,假设方法为int getBottom(stack, top)

示例图如下

假设原始栈如下

image

调用int getBottom(stack, top)获取栈底元素 h 并返回栈底元素,然后把栈底元素删除,并把剩余元素压下来,栈变成如下样子

image

然后递归调用原函数,将剩余部分逆序

image

最后将之前的栈底元素放到原来的栈顶

image

即完成了栈的逆序

整个算法我们可以通过如下方式来实现

// 逆序一个栈
    public  int[] reverseStackRecursively(int[] stack, int top) {
        if (top >= 1) {
            // 获取栈底元素
            int bottom = getBottom(stack, top);
            // 逆序除了栈底的剩余部分
            stack = reverseStackRecursively(stack, --top);
            // 栈底放栈顶
            stack[top] = bottom;
        }
        return stack;
    }

接下来就是int getBottom(stack, top)的实现,由于此方法要实现的功能是

  1. 返回栈底元素

  2. 删掉栈底元素

  3. 其余元素压下来

且该函数也需要通过递归来实现,base case 是top == 1的时候,栈只有一个元素

直接返回stack[0]

接下来是普遍情况,通过

int tmp = stack[--top];

获取栈顶元素

然后

int bottom = getBottom(stack, top);

获取栈底元素,bottom 即为要返回的元素

最后

stack[--top] = tmp;

栈顶元素下降一格,表示压下来这个动作。

完整代码如下

import java.util.*;

public class ReverseStack {
    public  int[] reverseStackRecursively(int[] stack, int top) {
        if (top >= 1) {
            // 获取栈底元素
            int bottom = getBottom(stack, top);
            // 逆序
            stack = reverseStackRecursively(stack, --top);
            // 栈底放栈顶
            stack[top] = bottom;
        }
        return stack;
    }

    public  int getBottom(int[] stack, int top) {
        if (top == 1) {
            return stack[0];
        } else {
            int tmp = stack[--top];
            int bottom = getBottom(stack, top);
            stack[--top] = tmp;
            return bottom;
        }
    }
}

更多

算法和数据结构笔记

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号