JavaScript数据结构《栈》

nanchen2251 发布于2019-08-21 16:44 / 259人阅读

摘要：我们都知道数组是里面比较常用的一种数据结构，栈和数组类似，定义如下栈是一种遵从后进先出原则的有序集合。新增加和待删除的元素都保存在栈的尾部，也称栈顶，相反的另一端就叫栈底，在栈的这种数据结构里面，我们新增的元素都在栈顶，旧的元素都在栈底。

由于不是计算机专业出身，对数据结构这些了解的比较少，最近看了一些相关的书籍，这里做一些总结。本篇要说的是栈。我们都知道数组是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全栈教程 javascript全栈开发 javascript快速全栈开发

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/88657.html

javasctipt 工作原理之调用栈

摘要：译者注翻译一个对新手比较友好的工作原理解析系列文章注意以下全部是概念经验丰富的老鸟可以离场啦正文从这里开始随着的流行团队们正在利用来支持多个级别的技术栈包括前端后端混合开发嵌入式设备以及更多这篇文章旨在成为深入挖掘和实际上他是怎么工作的系列译者注翻译一个对新手比较友好的 JavaScript 工作原理解析系列文章注意: 以下全部是概念,经验丰富的老鸟可以离场啦正文从这里开始随...

Pines_Cheng 2019-08-23 10:38 评论0 收藏0
前端进击的巨人（二）：栈、堆、队列、内存空间

摘要：中有三种数据结构栈堆队列。前端进击的巨人一执行上下文与执行栈，变量对象中解释执行栈时，举了一个乒乓球盒子的例子，来演示栈的存取方式，这里再举个栗子搭积木。对于基本类型，栈中存储的就是它自身的值，所以新内存空间存储的也是一个值。面试经常遇到的深浅拷贝，事件轮询，函数调用栈，闭包等容易出错的题目，究其原因，都是跟JavaScript基础知识不牢固有关，下层地基没打好，上层就是豆腐渣工程，...

edgardeng 2019-08-23 14:43 评论0 收藏0
[译文] JavaScript工作原理：引擎、运行时、调用栈概述

摘要：调用栈是单线程编程语言，意味着它只有单一的调用栈。调用栈是一种数据结构，基本记录了程序运行的位置。举个例子，先来看如下所示的代码当引擎开始执行这段代码时，调用栈将是空的。这正是抛出异常时栈追踪的构造过程这基本上就是异常抛出时调用栈的状态。原文 How JavaScript works: an overview of the engine, the runtime, and the c...

PAMPANG 2019-08-23 17:04 评论0 收藏0
理解 JavaScript 执行栈

摘要：执行栈所有的代码在运行时都是在执行上下文中进行的。引擎执行栈顶的函数，执行完毕，弹出当前执行上下文。但是这里我们也可以用执行栈来解释。这是 JavaScript 系列的第 3 篇。引例首先来看一个引例： function foo() { console.log(1); bar(); console.log(3); } function bar() { conso...

yacheng 2019-08-23 14:01 评论0 收藏0
【Javascript】探究javascript中的堆/栈/任务队列与并发模型 event loop

摘要：而函数调用结束返回时，运行时会将栈顶的调用结构弹出。并发模型与引擎是单线程的，它的并发模型基于事件循环当线程中的同步任务执行完，执行栈为空时，则从任务队列中取出异步任务进行处理。在当前的微任务没有执行完成时，是不会执行下一个宏任务的。堆/栈/队列在javascript中，存在调用栈 (call stack)和内存堆(memory heap) ,程序中函数依次进入栈中等待执行,若执行...

desdik 2019-08-26 13:47 评论0 收藏0