[ JavaScript ] 数据结构与算法 —— 栈

前言

JavaScript是当下最流行的编程语言之一，它可以做很多事情：

• 数据可视化（D3.js，Three.js，Chart.js）;
• 移动端应用(React Native,Weex,AppCan,Flutter,Hybrid App,小程序);
• 服务端(Express.js,Koa2)；
• 桌面应用(Electron,nw.js);
• 游戏,VR，AR(LayaAir,Egret,Turbulenz,PlayCanvas);
• 等等。。。

而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。

本篇主要有三部分

• 什么是栈
• 栈的实现
• 栈的应用

源码地址： https://github.com/yhtx1997/S...

什么是栈

较官方解释

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的

同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

个人理解

上面看不懂？没关系，接下来我用生活中比较常见的事来解释。

大家应该都搬过家，旅行，或者上学时住宿，这个过程中都会用到行李箱。

• 栈：现在这个旅行箱就是我们的栈；
• 栈里边的元素：我们往旅行箱放叠好的衣服或其他的东西，这些东西就是栈里边的元素；
• 栈底：我们放衣服时都是是先放旅行箱的最底下，不可能说什么东西都没有就让它飘着是吧，这个旅行箱最底下衣服在的位置就是栈底
• 栈顶：相对应的最后放进去的一件衣服的位置就是栈顶；
• 压栈：把元素放进去（把衣服放进旅行箱）的动作就是压栈；
• 出栈：把元素拿出来（把衣服拿出来）的动作就是出栈；
• 堆栈溢出：一般是指栈满了放不下了（旅行箱满了怎么塞塞不下了）；
• 后进先出：放衣服时一件一件的放，但是往外拿衣服的时候是先拿放的时候最后放的，最后拿出来的是放的时候最先放的；可能有人拿衣服直接翻到最下边然后拿出来，这个过程可以看做，先将除了栈底的元素依次出栈并保存，等拿到栈底的元素在依次压栈，把元素放回去
• 有序集合：额，就是一个挨着一个，有顺序的，一些有相同属性的东西

栈的实现

• 添加元素
• 删除元素
• 返回栈顶元素
• 是否为空
• 元素数量
• 清空元素
• 打印所有元素

class Stack {
    constructor() {
        this.count = 0; // 长度
        this.items = {}; // 栈
    }
    push(element) {
        // 添加元素
    }
    pop() {
        // 删除元素
    }
    peek() {
        // 返回栈顶元素
    }
    isEmpty() {
        // 是否为空
    }
    size() {
       // 元素数量
    }
    clear() {
       // 清空元素
    }
    toString() {
       // 打印所有元素
    }
}

添加元素

push(element) {
    this.items[this.count] = element;
    this.count++; // 长度加1
}

删除元素

pop() {
    if (this.isEmpty()) { // 如果是空直接返回 undefined
        return undefined;
    }
    this.count--;
    let item = this.items[this.count];
    delete this.items[this.count];
    return item
}

返回栈顶元素

peek() {
    if (this.isEmpty()) {
        return undefined;
    }
    return this.items[this.count - 1];
}

是否为空

isEmpty() {
    return this.count === 0;
}

元素数量

size() {
    return this.count;
}

清空元素

clear() {
    this.count = 0;
    this.items = {};
}

打印所有元素

toString() {
    if (this.isEmpty()) {
        return '';
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
        objString = `${objString},${this.items[i]}`;
    }
    return objString;
}

栈的应用

• 进制转换
• 括号匹配检验
• 迷宫求解

进制转换

栈因为是先进后出，所以如果将一组数据全部压栈，再出栈并保存每次出栈的元素，这样一来相当于将这一组元素的顺序进行倒序。

十进制转换二进制的过程就是一个数除以2，取余数，最后将余数结果进行倒序排列。

现在栈可以进行倒序，而进制转换需要倒序，所以就可以将栈应用到进制的转换中。

代码如下：

function DecimalToBinary(number) {
    let stack = new Stack(); // 新建栈
    let rem = 0; // 余数
    let binary = ''; // 结果
    while (number > 0) {
        rem = Math.floor(number % 2); // 取余数
        stack.push(rem); // 将余数压栈
        number = Math.floor(number / 2); // 去掉余数除以二
    }
    while (!stack.isEmpty()) { // 不为空
        binary += stack.pop(); // 将元素全部出栈
    }
    return binary;
}

括号匹配检验

正常括号嵌套是这样的

{{{[([({()})])]}}}

可以发现，在某个位置分为了左右两部分，右边第一个，与左边最后一个相对应

右边最后一个与左边第一个相对应

左侧相当于进行了倒序，而倒序就可以用栈来解决

我们可以将所有的左侧括号都依次压入栈中，然后依次判断右侧是否与栈顶元素相匹配

但是相匹配的括号并不相等

可以采用键值对的形式存储一下

{
    '}': '{',
    ']': '[',
    ')': '('
}

或者下标的形式

['{','[','(']
['}',']',')']

最终代码如下

function parenthesesChecker(symbols) {
    let stack = new Stack(); // 新建栈
    let balanced = true; // 检验括号匹配是否正确
    const leftBrackets = '{[('; // 左侧的括号
    const rightBrackets = '}])'; // 右侧的括号
    for (let i = 0; i < symbols.length && balanced; i++) {
        current = symbols[i]; // 取单个符号
        if (leftBrackets.indexOf(current) >= 0) { // 如果是左侧的括号
            stack.push(current); // 将其压栈
        } else if (stack.isEmpty()) { // 不是左侧括号，且栈为空，括号匹配错误
            balancd = false;
        } else { // 不是左侧括号，且栈不为空，视为没有新的左侧括号，剩下的都是右侧括号
            let top = stack.pop();
            if (!(leftBrackets.indexOf(top) === rightBrackets.indexOf(current))) { 
            // 检查栈顶（最后一个左侧括号）符号在 leftBrackets 的位置以及当前符号在 rightBrackets 的位置，位置相同视为配对成功
                balanced = false;
            }
        }
    }
    
    return balanced; // 返回结果
}

迷宫求解

这个比较复杂，之后会写个小实例，敬请期待......