用递归函数和栈操作逆序栈
2023-02-18 16:35:16 时间
用递归函数和栈操作逆序栈
作者:Grey
原文地址:
题目描述
请设计一个算法实现逆序栈的操作,但是只能用递归函数来实现,而不能用另外的数据结构。给定一个栈Stack以及栈的大小top,请返回逆序后的栈。
题目链接:牛客-用递归函数和栈操作逆序栈
首先,如果我们可以用递归函数实现这样的功能:获取一个栈的栈底元素并返回栈底元素,然后把栈底元素删除,并把剩余元素压下来,假设方法为int getBottom(stack, top)
示例图如下
假设原始栈如下
调用int getBottom(stack, top)
获取栈底元素 h 并返回栈底元素,然后把栈底元素删除,并把剩余元素压下来,栈变成如下样子
然后递归调用原函数,将剩余部分逆序
最后将之前的栈底元素放到原来的栈顶
即完成了栈的逆序
整个算法我们可以通过如下方式来实现
// 逆序一个栈
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)
的实现,由于此方法要实现的功能是
-
返回栈底元素
-
删掉栈底元素
-
其余元素压下来
且该函数也需要通过递归来实现,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;
}
}
}
更多
相关文章
- 如何面向对象编程?程序员:我也要先有“对象”啊
- 设计一个可扩展的用户登录系统 (3)
- 设计一个可扩展的用户登录系统 (2)
- 彪悍的职业不惧阿尔法狗
- 沉默的大多数
- 在Ubuntu Server上编译FFmpeg
- 素食,跑步,修行
- 2016厦门马拉松胜利完赛
- 秋游红叶岭
- 如何完成一个全程马拉松
- 设计一个可扩展的用户登录系统 (1)
- 愤怒的小怪兽
- 推荐:七周七并发模型
- 当你遇到一个巨大的代码库,你应该怎么办
- Clojure驱动的Web开发
- 给Nginx配置一个自签名的SSL证书
- 如何正确地处理时间
- 如何在一个页面上让多个jQuery版本共存
- npm install canvas简明指南
- 不使用UINavigationController实现Push动画