欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常见面试算法题JS实现-仅用递归函数和栈操作逆序一个栈

程序员文章站 2022-03-23 08:43:01
前言: 因为JAVA和JS语言特性的不同,有些东西在JAVA中可能需要一些技巧和手段才能实现的复杂程序,但是在JS中可能就是天然存在的,所以这套书里面的题目不会全部用JS去实现一遍,因为可能JS的实现太过于简单,以至于写出来没有太多意义,而有些可能会实现结果和书中JAVA实现非常相似,而后者的话,我 ......

前言:

  因为JAVA和JS语言特性的不同,有些东西在JAVA中可能需要一些技巧和手段才能实现的复杂程序,但是在JS中可能就是天然存在的,所以这套书里面的题目不会全部用JS去实现一遍,因为可能JS的实现太过于简单,以至于写出来没有太多意义,而有些可能会实现结果和书中JAVA实现非常相似,而后者的话,我还是会重新用JS实现一遍,就当时练习敲代码了吧~

 

正文:

  【题目】一个栈依次压入1、2、3、4、5,那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后,从栈顶到栈底为1、2、3、4、5,也就是实现栈中元素的逆序,但只能用递归实现,不能用其他数据结构。

  【实现】

 1 class ReverseStack {
 2     constructor() {
 3         //初始化一个栈
 4         this.stack = arguments[0]
 5     }
 6     reverse() {
 7         //用递归的方式反转栈
 8         if (this.stack.length === 0) {
 9             return
10         } else {
11             //取出栈底元素
12             let i = this._getAndRemoveLastElement()
13             //然后反转栈
14             this.reverse()
15             //最后压入之前的栈底元素,此时该元素变成了栈顶元素
16             this.stack.push(i)
17         }
18     }
19     _getAndRemoveLastElement() {
20         //⬆此方法命名表示内部私有函数,以不同的命名方式以做区分
21         //将栈顶元素弹出
22         var res = this.stack.pop()
23         //如果此时栈空,则该元素为栈底元素,直接返回
24         if (this.stack.length === 0) {
25             return res
26         } else {
27             //若栈不空,则继续弹出元素,直到返回栈底元素
28             var last = this._getAndRemoveLastElement()
29             //再依次将之前弹出的元素压入栈中
30             this.stack.push(res)
31             return last
32         }
33     }
34     showStack() {
35         //查看当前栈元素
36         console.log(this.stack)
37     }
38 }
39 
40 //初始化一个递归反转栈
41 var rs = new ReverseStack([1,2,3,4,5])
42 //查看当前栈元素
43 rs.showStack()
44 //反转
45 rs.reverse()
46 //查看反转后栈元素
47 rs.showStack()

 

后话:

  emmmm,没啥好说的,激励一下自己吧:算法很有意思,希望能够坚持把这本书撸完~