常见面试算法题JS实现-仅用递归函数和栈操作逆序一个栈
程序员文章站
2022-07-01 20:40:20
前言: 因为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,没啥好说的,激励一下自己吧:算法很有意思,希望能够坚持把这本书撸完~