第七十九期：数据结构（栈）
栈
栈是一种很常见的数据结构。先进后出即last in first out 是她的特性。有一些语言内置了栈的数据结构，比如c。但是js中并没有内置这种数据结构，但是这并不影响我们进行开发，我们可以自己实现，并且运用它。
栈的方法一般有这几个：
- push
- pop
- peek
- clear
- size
栈的结构则如图所示：
书上的demo一般都用数组来实现栈。但是我们很少去想一个问题，为什么数组完全可以实现栈的所有功能，但是还要去实现栈呢？实现栈的真正的目的是什么呢？
因为栈这种结构，使得我们的应用程序更加语义化。假设我们有一个书包和一个钱包。我们可以把钱放在书包里，也可以把钱放在钱包里。但是放在书包里的话，从外面看，我们不一定知道它里面装的是钱。但是放在钱包里，我们一眼就能知道它里面装的是钱，甚至知道它装的是人民币还是美元。
另外，原生的数组API具有不同的时间复杂度。比如array.prototype.slice在最坏的情况下时间复杂度为o（n），因为它需要遍历所有的索引，并且在数组中拼接时重新进行调整。而push方法在内存缓冲区满的时候，复杂度也为o（n）。
而栈这种结构避免了直接访问元素，在内部依赖于WeakMap（），这种内存效率是很高的。
栈的实现
我们可以是使用es6的方法来实现它。
const sKey = {}
const items = new WeakMap()
class Stack{
constructor(){
item.set(sKey,[])
}
push(element){
let stack = items.get(sKey)
stack.push(element)
}
pop(){
let stack = item.get(sKey)
return stack.pop()
}
clear(){
items.set(sKey,[])
}
size(){
return items.get(sKey).length
}
}
然后我们可以这样写：
let Stack = (()=>{
const sKey = {}
const items = new WeakMap()
class Stack{
constructor(){
items.set(sKey,[])
}
push(element){
let stack = items.get(sKey)
stack.push(element)
}
pop(){
let stack = items.get(sKey)
return stack.pop()
}
peek(){
let stack = items.get(sKey)
return stack[stack.length-1]
}
clear(){
items.set(sKey,[])
}
size(){
return items.get(sKey).length
}
}
return Stack
})()
我们把stack类封装在一个匿名函数中，并且这个函数是个立即调用函数。
这种写法之前我一直很疑惑，为什么要这样写？其实就是为了防止变量的污染,定义的sKey，和items 只有内部的class类可以用，其他地方都用不了。
当然，我们也可以直接定义到类的构造函数中：
constructor(){
this.sKey = {}
this.items = new WeakMap()
this.items.set(sKey,[])
}
这种写法会使得items在外部也可以被访问。
全局使用
想要在全局使用我们定义的stack类，如果我们直接引用，多少显的有点low，我们可以写个装b的写法，判断一下运行环境，然后直接给它添加到全局。
这样就可以避免了复制一堆重复的代码，顺带着也做了运行环境的兼容。
// AMD
if(typeof define === 'function' && define.amd){
define(function(){return Stack});
// NodeJs/CommonJs
}eles if(typeof exports === 'object'){
if(typeof module ==='object' && typeof module.exports==='object'){
exports = module.exports = Stack;
}
// 浏览器
}else{
window.Stack = Stack
}
这样写是不是好多了？兼容了多个环境，还显得我们的代码有水平，但更重要的是这种思维确实可以提高我们的编码水平。
实际应用
实际应中的场景，在前端业务开发中似乎也并不常见。但是在vue-router的源码的实现中，抽象history的实现用了栈的概念，但是本质上还是用数组实现的这个功能。
export class AbstractHistory extends History {
index: number
stack: Array<Route>
constructor (router: Router, base: ?string) {
super(router, base)
this.stack = []
this.index = -1
}
push (location: RawLocation, onComplete?: Function, onAbort?: Function) {
this.transitionTo(
location,
route => {
this.stack = this.stack.slice(0, this.index + 1).concat(route)
this.index++
onComplete && onComplete(route)
},
onAbort
)
}
}
剩下的场景就是在编译解析的过程中会用到栈，因为栈的性能相对数组会好很多。
关于栈，先说这么多吧，等我找个比较好的例子再具体的解释一下具体的场景和使用过程。
本文分享自 JavaScript高级程序设计 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
腾讯云开发者
