JavaScript数据结构《栈》

发布时间:2019-08-20 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了JavaScript数据结构《栈》脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

由于不是计算机专业出身,对数据结构这些了解的比较少,最近看了一些相关的书籍,这里做一些总结。本篇要说的是栈。我们都知道数组是JavaScript里面比较常用的一种数据结构,栈和数组类似,定义如下

栈是一种遵从后进先出 (LIFO) 原则的有序集合。 新增加和待删除的元素都保存在栈的尾部,也称栈顶,相反的另一端就叫栈底,在栈的这种数据结构里面,我们新增的元素都在栈顶,旧的元素都在栈底。

举一个生活中的例子,我们平时完饭洗盘子的时候,我们都会把洗好的盘子一个个堆叠起来,先放进去的盘子就是我们栈里面比较旧的元素(栈底),后放的盘子就是比较新的盘子(栈顶),然后我们要把一个盘子拿下来的时候我们都是从上面开始拿(栈顶),这里就是后放进去的盘子先拿出来了,所以这里就遵循了后进先出 (LIFO) 的原则了。

代码实现

代码全部采用ES6的语法,首先我们定义一个类Stack来表示栈,然后为该类实现一些方法来模拟栈的行为

class Stack {

  constructor() {
    // 定义一个数组来保存栈里面的元素
    this.ITems = []
  }

  // 添加元素到栈顶
  push() { }
  // 从栈顶移除元素,同时返回被移除元素
  pop() { }
  // 返回栈顶的元素,不对栈本身做修改
  PEek() { }
  // 判断栈是否为空
  iSEMpty() { }
  // 清空栈
  remove() { }
  // 返回栈里面元素的个数
  length() { }
}

这样我们就定义好一个基类了,下面来分别实现栈的行为方法

push

我们要实现的第一个方法(行为)就是push,push方法会向栈的栈顶新增元素,因为我们是用数组来保存栈里面的元素的,所以这个方法的实现很简单,直接用JavaScript数组的push方法就好了。

push(item) {
    this.items.push(item)
}

pop

接下来要实现是pop方法(行为),pop会移除栈顶的元素并且会返回被移除的元素,这个方法我们同样可以用JavaScript数组的pop方法来实现

pop() {
    return this.items.pop()
}

peek

peek方法(行为)返回栈顶的最后一个元素,不对栈本身做修改,我们可以用Array.length-1获取数组的最后一个元素,所以peek方法可以这样写

peek() {
    return this.items[this.items.length-1]
}

isEmpty

isEmpty方法用来判断栈是否为空,用数组来表示就是数组的 length 是否等于0,所以我们可以得出如下代码

isEmpty() {
    return this.items.length === 0
}

remove

remove 方法用来清空栈里面所有的元素,实现这个方法是最简单的了,直接让数组等于一个新的空数组就好了

remove() {
    this.items = []
}

length

最后要实现的是length方法,length方法返回栈的大小,这个同样可以用数组的length来实现

length() {
    return this.items.length
}

这里我们添加一个辅助PRint方法来打印栈里面的元素,方便我们观察调试,这个方法和栈的行为无关,只是一个辅助方法

print(){
    this.items.foreach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
}

最后完整的代码如下

class Stack {

  constructor() {
    this.items = []  // 定义一个数组来保存栈里面的元素
  }
  // 添加元素到栈顶
  push(item) {
    this.items.push(item)
  }
  // 从栈顶移除元素,同时返回被移除元素
  pop() {
    return this.items.pop()
  }
  // 返回栈顶的元素,不对栈本身做修改
  peek() {
    return this.items[this.items.length-1]
  }
  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0
  }
  // 清空栈
  remove() {
    this.items = []
  }
  // 返回栈里面元素的个数
  length() {
    return this.items.length
  }

  print() {
    this.items.forEach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
  }
}

这样这个栈就基本实现了,下面来实际运行一下实现好的这个Stack类,首先我们需要实例化这个类,然后分别调用实例的方法来查看效果

const myStack = new Stack()  //  实例化

myStack.isEmpty() // true

myStack.push('这是栈的第一个元素') 
myStack.push('这是栈的第二个元素') 

myStack.print() // 1: 这是栈的第一个元素 2:这是栈的第二个元素

myStack.peek() // 这是栈的第二个元素

myStack.pop() // 这是栈的第一个元素

myStack.length() // 1

myStack.isEmpty() // false

myStack.remove() // 这时栈里面已经没有元素了

myStack.isEmpty() // true

栈的基本说明就到此了,下篇会总结一下和栈类似的数据结构,队列。

脚本宝典总结

以上是脚本宝典为你收集整理的JavaScript数据结构《栈》全部内容,希望文章能够帮你解决JavaScript数据结构《栈》所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。