Javascript中你应该知道的栈
目录
什么是栈
栈(stack)又名堆栈,是一种遵循后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的末尾,称作栈顶,另一端称作栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
现实记忆:好比我们把一摞叠起来的盘子都可以看做一个栈,我们想要拿出最底下的盘子,一定要现将上面的移走才可以。
栈结构的代码实现
在 Javascript 中我们可以使用数组的原生方法实现一个栈/队列的功能,鉴于学习目的,我们也使用类来实现一个栈,下面分别进行讲解
数组实现一个栈结构
function Stack() { /** * 用数组来模拟栈 */ var items = []; /** * 将元素送入栈,放置于数组的最后一位 */ this.push = function(element) { items.push(element); }; /** * 弹出栈顶元素 */ this.pop = function() { return items.pop(); }; /** * 查看栈顶元素 */ this.peek = function() { return items[items.length - 1]; } /** * 确定栈是否为空 * @return {Boolean} 若栈为空则返回 true,不为空则返回 false */ this.isAmpty = function() { return items.length === 0 }; /** * 清空栈中所有内容 */ this.clear = function() { items = []; }; /** * 返回栈的长度 * @return {Number} 栈的长度 */ this.size = function() { return items.length; }; /** * 以字符串显示栈中所有内容 */ this.print = function() { console.log(items.toString()); }; }
类实现一个栈结构
类实现
class Stack { constructor() { this.items = [] } // 入栈 push(element) { this.items.push(element) } // 出栈 pop() { return this.items.pop() } // 末位 get peek() { return this.items[this.items.length - 1] } // 是否为空栈 get isEmpty() { return !this.items.length } // 栈长度 get size() { return this.items.length } // 清空栈 clear() { this.items = [] } // 打印栈数据 print() { console.log(this.items.toString()) } }
使用栈类
// 实例化一个栈 const stack = new Stack() console.log(stack.isEmpty) // true // 添加元素 stack.push(5) stack.push(8) // 读取属性再添加 console.log(stack.peek) // 8 stack.push(11) console.log(stack.size) // 3 console.log(stack.isEmpty) // false
栈在实际开发中的应用
二进制转为十进制
/** * decNumber 要转换的十进制数字 * base 目标进制基数 */ function baseConverter(decNumber, base) { var remStack = new Stack(), rem, baseString = '', digits = '0123456789ABCDEF'; white (decNumber > 0) { rem = Math.floor(decNumber % base); remStack.push(rem); decNumber = Math.floor(decNumber / base); } white(JSON.stringify(remStack) != "{}") { baseString += digits[remStack.pop()]; } return baseString; }
JS 中的函数调用
栈也被用在编程语言的编译器和内存中保存变变量、函数调用。调用栈(Call Stack)
调用栈(Call Stack)是一个基本的计算机概念,这里引入一个概念:栈帧。
栈帧是指为一个函数调用单独分配的那部分栈空间。
当运行的程序从当前函数调用另外一个函数时,就会为下一个函数建立一个新的栈帧,并且进入这个栈帧,这个栈帧称为当前帧。而原来的函数也有一个对应的栈帧,被称为调用帧。每一个栈帧里面都会存入当前函数的局部变量。
栈帧结构示意图
当函数被调用时,就会被加入到调用栈顶部,执行结束之后,就会从调用栈顶部移除该函数。并将程序运行权利(帧指针)交给此时栈顶的栈帧。这种后进后出的结构也就是函数的调用栈。而在 JavaScript 里,可以很方便的通过 console.trace()这个方法查看当前函数的调用帧
说明:从上面的调用可以看出来,函数的调用也是有成本的,如果函数嵌套调用的越多所消耗的资源,栈数据也就越大
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。
码云笔记 » Javascript中你应该知道的栈
码云笔记 » Javascript中你应该知道的栈