数据结构-栈

栏目: JavaScript · 发布时间: 5年前

内容简介:数组是 JS 中最常用的数据结构,它可以在任意位置添加或删除数据。栈是另外一种数据结构,类似于数组,但是在添加或删除数据时更加灵活。栈是一种可以用数组来模拟一个栈结构:

前言

数组是 JS 中最常用的数据结构,它可以在任意位置添加或删除数据。栈是另外一种数据结构,类似于数组,但是在添加或删除数据时更加灵活。

栈数据结构

栈是一种 后进先出(LIFO) 的数据结构。新添加或待删除的元素都保存在栈的一端,叫 栈顶 ,另一端就叫做 栈底 。在栈中,新元素都靠近栈顶,就元素都靠近栈底。

创建栈

可以用数组来模拟一个栈结构:

function Stack() {
    let items = []
    // 栈的属性和方法
}

需要实现的方法:

  • push(element): 添加一个元素到栈顶
  • pop(): 移除栈顶的元素,并返回该元素
  • peek(): 仅仅返回栈顶的元素
  • clear(): 清空栈
  • size(): 返回栈中的元素的个数
  • isEmpty(): 判断栈是否为空
// 向栈中添加元素
this.push = function (element) {
    items.push(element)
}
// 从栈中移除元素
this.pop = function () {
    return items.pop()
}
// 查看栈顶元素
this.peek = function () {
    return items[item.length - 1]
}
// 检查栈是否为空
this.isEmpty = function () {
    return !!item.length
}
// 清空栈中的元素
this.clear = function () {
    items = []
}
// 返回栈的大小
this.size = function () {
    return items.length
}
// 打印栈
this.print = function () {
    console.log(items.toString())
}

ES6 与 栈

ES6 的写法:

class Stack {
    constructor() {
        this.items = []
    }
    push (element) {
        this.items.push(element)
    }
    // ... 其他方法
}

ES6 的类是基于原型的,虽然基于原型的类比基于函数的类更节省内存,但是却不能声明私有变量,所以变量 items 是公共的。这种情况下,可以直接通过修改 items 来修改栈中的数据,这是无法避免的。

用 ES6 的限定作用域 Symbol 实现类

ES6 新增了 Symbol 基础类型,它是不可变的,也可以作用对象的属性。

let _items = Symbol()
class Stack {
    constructor() {
        this[_items] = []
    }
    // ... 其他方法
}

上面这个例子创建了一个假的私有属性,不能完全规避上面提到的问题,因为 ES6 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性,比如:

let stack = new Stack()
stack.push(66)
stack.push(88)
let objectSymbols = Object.getOwnPropertySymbols(stack)
console.log(objectSymbols.length) // 1
console.log(objectSymbols[0]) // Symbol()
stack[objectSymbols[0]].push(1)
stack.print() // 66 88 1

通过访问 stack[objectSymbols[0]] 是可以访问 _items 的,并且可以对 _items 进行任意操作。

用 ES6 的WeakMap 实现类

有一种数据类型可以确保属性是私有的,这就是 WeakMap 。WeakMap 可以存储键值对,其中键是对象,值可以是任意数据类型。

const items = new WeakMap()
class Stack {
    constructor() {
        items.set(this, [])
    }
    push(element) {
        let s = items.get(this)
        s.push(element)
    }
    pop() {
        let s = items.get(this)
        return s.pop()
    }
    // ... 其他方法
}

现在,Stack 中的 items 是私有的了,但是 items 是在 Stack 类以外声明的,还是可以被改动,所以需要借助闭包来实现一层封装:

let Stack = (function () {
    const items = new WeakMap()
    class Stack {
    constructor() {
        items.set(this, [])
    }
    // ... 其他方法
    return Stack
}
})()

### 用栈解决实际问题

栈在 JS 中应用还是十分广泛的,比如 调用栈 。进制转换也是很常见的例子,可以用 栈 来处理,比如要把十进制转化成二进制,可以将该十进制数字和2整除,直到结果是 0 为止。

function divideBy2 (decNumber) {
    var remStack = new Stack(),
        rem,
        binaryString = ''
   
   while (decNumber > 0) {
       rem = Math.floor(decNumber % 2)
       remStack.push(rem)
       decNumber = Math.floor(decNumber / 2)
   }
   while (!remStack.isEmpty()) {
       binaryString += remStack.pop().toString()
   }
   return binaryString
}

这个例子中,当结果满足和2做整除的条件是,会取得当前结果和2的余数,放到栈里,然后让结果继续和2做整除。

#### 改进算法

把上面的例子改成十进制转成任意进制的:

function baseConverter(decNumber, base) {
     var remStack = new Stack(),
        rem,
        binaryString = '',
        digits = '0123456789ABCDEF'
   
     while (decNumber > 0) {
        rem = Math.floor(decNumber % base)
        remStack.push(rem)
        decNumber = Math.floor(decNumber / base)
     }
     while (!remStack.isEmpty()) {
        binaryString += digits[remStack.pop()]
     }
   return binaryString
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法引论

算法引论

[美]乌迪·曼博(Udi Manber) / 黄林鹏、谢瑾奎、陆首博、等 / 电子工业出版社 / 2010-1 / 36.00元

本书是国际算法大师乌迪·曼博(Udi Manber)博士撰写的一本享有盛誉的著作。全书共分12章:第1章到第4章为介绍性内容,涉及数学归纳法、算法分析、数据结构等内容;第5章提出了与归纳证明进行类比的算法设计思想;第6章到第9章分别给出了4个领域的算法,如序列和集合的算法、图算法、几何算法、代数和数值算法;第10章涉及归约,也是第11章的序幕,而后者涉及NP完全问题;第12章则介绍了并行算法;最后......一起来看看 《算法引论》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具