重读《学习JavaScript数据结构与算法-第三版》- 第4章 栈

  • 2019 年 10 月 3 日
  • 筆記

定场诗

金山竹影几千秋，云索高飞水自流；  万里长江飘玉带，一轮银月滚金球。  远自湖北三千里，近到江南十六州；  美景一时观不透，天缘有分画中游。

前言

本章是重读《学习JavaScript数据结构与算法-第三版》的系列文章，本章为各位小伙伴分享数据结构-栈的故事，请让胡哥带你走进栈的世界

栈

何为栈？栈是一种遵从后进先出（LIFO）原则的有序集合。

新添加或待删除的元素都保存在栈的同一端，称作栈顶；另一端就叫栈底。

在栈里，新元素都靠近栈顶，旧元素都接近栈底。

基于数组的栈

我们将创建一个基于数组的栈，了解栈的结构、运行规则

/**   * 基于数组array的栈Stack   * @author huxiaoshuai   */  class Stack {    // 初始化    constructor () {      this.items = []    }  }

使用数组保存栈里的元素

数组允许我们在任何位置添加和删除元素，那基于栈遵循LIFO原则，我们对元素的插入和删除功能进行封装

方法 描述
push(element(s)) 添加一个（或多个）新元素到栈顶
pop() 移除栈顶元素，同时返回被移除的元素
peek() 返回栈顶的元素，不对栈做任何修改
isEmpty() 判断栈是否为空，为空则返回true，否则返回false
clear() 移除栈的所有元素
size() 返回栈的元素个数

代码实现

class Stack {    // 初始化    constructor () {      this.items = []    }      /**     * push() 添加元素到栈顶     */    push (element) {      this.items.push(element)    }      /**     * pop() 移除栈顶元素并返回     */    pop () {      return this.items.pop()    }      /**     * peek() 返回栈顶部元素     */    peek () {      return this.items[this.items.length - 1]    }      /***     * isEmpty() 检测栈是否为空     */    isEmpty () {      return this.items.length === 0    }      /**     * size() 返回栈的长度     */    size () {      return this.items.length    }      /**     * clear() 清空栈元素     */    clear () {      this.items = []    }  }

使用Stack类

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    stack.push(15)

基于以上栈操作的示意图
基于以上栈操作的示意图

stack.pop()  stack.pop()  console.log(stack.size()) // 2

基于以上栈操作的示意图
基于以上栈操作的示意图

基于对象的栈

创建一个Stack类最简单的方式是使用一个数组来存储元素。在处理大量数据的时候，我们同样需要评估如何操作数据是最高效的。

使用数组时，大部分方法的时间复杂度是O(n)。简单理解：O(n)的意思为我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的n代表数组的长度。数组越长，所需时间会更长。另外，数组是元素的一个有序集合，为保证元素的有序排列，会占用更多的内存空间。

使用JavaScript对象来存储所有的栈元素，以实现可以直接获取元素，同时占用较少的内存空间，同时保证所有的元素按照我们的需要进行排列，遵循后进先出（LIFO）原则。

代码实现

/**   * 基于对象的Stack类   * @author huxiaoshai   */  class Stack {    // 初始化    constructor () {      this.items = {}      this.count = 0    }      /**     * push() 向栈中添加元素     */    push (element) {      this.items[this.count] = element      this.count++    }      /**     * isEmpty() 判断是否为空     */    isEmpty () {      return this.count === 0    }      /**     * size() 返回栈的长度     */    size () {      return this.count    }      /**     * pop() 栈顶移除元素并返回     */    pop () {      if (this.isEmpty()) {        return undefined      }      this.count--      let result = this.items[this.count]      delete this.items[this.count]      return result    }      /**     * peek() 返回栈顶元素，如果为空则返回undefined     */    peek () {      if (this.isEmpty()) {        return undefined      }      return this.items[this.count - 1]    }      /**     * clear() 清空栈数据     */    clear () {      this.items = {}      this.count = 0    }      /**     * toString() 实现类似于数组结构打印栈内容     */    toString () {      if (this.isEmpty()) {        return ''      }      let objStr = `${this.items[0]}`      for (let i = 1; i < this.count; i++) {        objStr = `${objStr},${this.items[i]}`      }      return objStr    }  }

保护数据结构内部元素

私有属性

有时候我们需要创建供其他开发者使用的数据结构和对象时，我们希望保存内部元素，只有使用允许的方法才能修改内部结构。很不幸，目前JS是没有办法直接声明私有属性的，目前业内主要使用一下几种方式实现私有属性。

  1. 下划线命名约定

    class Stack {    constructor () {      this._items = {}      this._count = 0    }  }

    这只是约定，一种规范，并不能实际保护数据

  2. 基于ES6的限定作用域Symbol实现类

    const _items = Symbol('stackItems')  class Stack {    constructor () {      this[_items] = []    }  }

    假的私有属性，ES6新增的Object.getOwnPropertySymbols方法能够获取类里面声明的所有Symbols属性

  3. 基于ES6的WeakMap实现类

    /**   * 使用WeekMap实现类的私有属性   */  const items = new WeakMap()  console.log(items) // WeakMap { [items unknown] }    class Stack {    constructor () {      items.set(this, [])    }      push (element) {      const s = items.get(this)      s.push(element)    }      pop () {      const s = items.get(this)      const r = s.pop()      return r    }      toString () {      const s = items.get(this)      return s.toString()    }  }    const stack = new Stack()  stack.push(1)  stack.push(2)  stack.push(3)    console.log(stack.toString()) // 1,2,3  console.log(stack.items) // undefined

    使用该方式，items是Stack类里的私有属性，但是此种方式代码的可读性不强，而且在扩展该类时无法继承私有属性。

  4. ECMAScript类属性提案

    有一个关于JavaScript类中增加私有属性的提案。通过在属性前添加井号(#)作为前缀来声明私有属性。

class Stack {    #count = 0    #items = []  }

使用栈来解决问题

栈的实际应用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作（后续会在讨论图和回溯问题时进一步详细讲解）。栈的使用场景有很多，如汉诺塔问题、平衡圆括号、计算机科学问题：十进制转二进制问题

/**   * decimalToBinary() 实现十进制转二进制的算法   */  function decimalToBinary (decNumber) {    // 实例化栈数据结构    const remStack = new Stack()    let number = decNumber    let rem;    let binaryString = ''      // 依次将获取的二进制数压入栈中    while (number > 0) {      rem = Math.floor(number % 2)      remStack.push(rem)      number = Math.floor(number / 2)    }    // 拼接要输出的二进制字符串    while (!remStack.isEmpty()) {      binaryString += remStack.pop().toString()    }    return binaryString  }    console.log(decimalToBinary(10)) // 1010  console.log(decimalToBinary(23)) // 10111

后记

以上就是胡哥今天给大家分享的内容，喜欢的小伙伴记得收藏、转发、点击右下角按钮在看，推荐给更多小伙伴呦，欢迎多多留言交流…

胡哥有话说，一个有技术，有情怀的胡哥！京东开放平台首席前端攻城狮。与你一起聊聊大前端，分享前端系统架构，框架实现原理，最新最高效的技术实践！

长按扫码关注，更帅更漂亮呦！关注胡哥有话说公众号，可与胡哥继续深入交流呦！

胡哥有话说

VirMach 便宜 VPS

QNews

QNews