JavaScript数据结构之-栈

ゝ一纸荒年。 2022-05-01 12:14 135阅读 0赞

#### 栈数据结构 ####

**栈** 是一种遵循 **后进先出（LIFO）** 原则的有序集合。新添加和待删除的数据都保存在栈的同一端**栈顶**，另一端就是**栈底**。新元素靠近栈顶，旧元素靠近栈底。

#### 创建一个栈 ####

我们需要自己创建一个栈，并且这个栈包含一些方法。

*  push(element(s)):添加一个（或多个）新元素到栈顶
 *  pop():删除栈顶的元素，并返回该元素
 *  peek():返回栈顶的元素，不对栈做任何操作
 *  isEmpty():检查栈是否为空
 *  size():返回栈的元素个数
 *  clear():清空栈

但是这样的方式在创建多个实例的时候为创建多个items的副本。就不太合适了。 用ES如何6实现Stack类了。可以用WeakMap实现，并保证属性是私有的。

#### 用栈解决问题 ####

栈可以解决十进制转为二进制的问题、任意进制转换的问题、平衡园括号问题、汉罗塔问题。

// 例子十进制转二进制问题
    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;
    }
    // 任意进制转换的算法
    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()].toString();
        }
        return binaryString;
    }
    复制代码

转载于:https://juejin.im/post/5cc86ae4e51d45400f5d58ae