数据结构-栈

zhoutk 发布于2019-08-23 14:59 / 2042人阅读

摘要：栈是另外一种数据结构，类似于数组，但是在添加或删除数据时更加灵活。栈数据结构栈是一种后进先出的数据结构。这种情况下，可以直接通过修改来修改栈中的数据，这是无法避免的。

前言

数组是 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
}

GPU云服务器云服务器栈结构栈数据结构栈顺序结构优化递归数据栈

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

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

js数据结构和算法（二）栈和队列

摘要：对于栈来说，这个表尾称为栈的栈顶，相应的表头称为栈底。栈和队列的区别栈的插入和删除操作都是在一端进行的，而队列的操作却是在两端进行的。出栈操作出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作。基本概念栈和队列都是动态的集合，在栈中，可以去掉的元素是最近插入的哪一个。栈实现了后进先出。在队列中，可以去掉的元素总是在集合中存在的时间最长的那一个。队列实现了先进先出的策略。栈的官...

jsummer 2019-08-21 12:30 评论0 收藏0
Java版-数据结构-栈

摘要：介绍栈是一种后进先出的线性表数据结构，分为栈顶和栈底两端，仅允许在表的一端插入元素，这一端被称为栈顶，另外一端称之为栈底。介绍栈是一种后进先出的线性表数据结构，分为栈顶和栈底两端，仅允许在表的一端插入元素，这一端被称为栈顶，另外一端称之为栈底。栈，只有两种操作，分为入栈（压栈）和出栈（退栈）；向栈中添加元素的操作叫做入栈，相反从栈中删除元素叫做出栈。特点只能从栈顶添加元素或者...

voidking 2019-08-16 16:10 评论0 收藏0
JavaScript数据结构《栈》

摘要：我们都知道数组是里面比较常用的一种数据结构，栈和数组类似，定义如下栈是一种遵从后进先出原则的有序集合。新增加和待删除的元素都保存在栈的尾部，也称栈顶，相反的另一端就叫栈底，在栈的这种数据结构里面，我们新增的元素都在栈顶，旧的元素都在栈底。由于不是计算机专业出身，对数据结构这些了解的比较少，最近看了一些相关的书籍，这里做一些总结。本篇要说的是栈。我们都知道数组是JavaScript里面...

nanchen2251 2019-08-21 16:44 评论0 收藏0
finally与return之间的关系

摘要：则会在转移指令前执行。总结与之间的关系如果在中含有语句，那么语句的还有作用吗先看一段代码如果你对内存布局不是很清楚，请看这篇文章虚拟机类加载机制和字节码执行引擎重点关注运行时栈帧结构局部变量表槽，操作数栈。定论问：finally语句一定会执行吗？答：如果没有执行相应的try语句则不会执行。在try语句中如果调用System.exit(0)方法则不会执行。问：finally...

Yuanf 2019-08-14 12:25 评论0 收藏0
JS数据结构学习：栈

摘要：栈的应用前面介绍了那么多栈相关的知识，最后也是介绍栈的应用场景的时候了，栈的实际应用非常广泛，例如用来存储访问过的任务或路径撤销的操作。栈的定义什么是栈？栈是一种遵循后进先出原则的有序集合，新添加的或者待删除的元素都保存在栈的同一端，称为栈顶，另一端称为栈底，在栈里，新元素靠近栈顶，旧元素靠近栈底，用个图来看大概这样式的：showImg(https://segmentfault.c...

Alfred 2019-08-26 13:28 评论0 收藏0
js 调用栈机制与ES6尾调用优化介绍

摘要：调用栈的运行机制机制程序运行到一个函数，它就会将其添加到调用栈中，当从这个函数返回的时候，就会将这个函数从调用栈中删掉。在调用栈中每个调用侦都对应一个函数，最上方的调用帧称为当前帧，调用栈是由所有的调用侦形成的。 showImg(https://segmentfault.com/img/remote/1460000019244497?w=900&h=600); 调用栈的英文名叫做Cal...

AaronYuan 2019-08-26 13:52 评论0 收藏0