栈

栈数据结构

栈是一种后进先出的有序集合，有栈顶和栈底。

创建栈

//创建一个类来表示栈
function Stack() {}

首先，我们可以用数组来保存栈里的元素：

let items = []

接下来要为栈声明一些方法：

push()、pop()、peek()、isEmpty()、clear()、size()。

向栈添加元素

this.push = function(element) {
    items.push(element)
};

从栈移除元素

this.pop = function() {
    return items.pop();
};

查看栈顶元素

this.peek = function() {
    return items[items.length - 1];
};

检查栈是否为空

this.isEmpty = function() {
    return items.length == 0;
};
this.size = function () {
    return item.length;
}

清空和打印栈元素

this.clear = function() {
    items = [];
};

栈已经完成，在添加一个print方法，输出栈里的元素：

this.print = function() {
    console.log(item.toString());
}

使用Stack类：

let stack = new Stack();
stack.push(5);
stack.push(8);
......

ES6和stack类

class Stack{
    constructor() {
        this.items = [];
    }
    push(element) {
        this.items.push(element);
    }
    ...
}

items变量是公共的，我们希望用户只能访问暴露给类的方法，否则就有可能从栈的中间移除元素(因为我们用数组来存储其值)，这不是我们希望看到的。

let a = new Stack();
a.items = [1,2,3,4,5]
a.items.splice(1,2)
console.log(a);    //Stack { items: [ 1, 4, 5 ] }

所以我们要创建私有属性：

// 1.用ES6的限定作用域Symbol实现类
let _items = Symbol();
class Stack {
    constructor() {
        this[_items] = []
    }
}

这个方法创建了一个假的私有属性，因为ES6的Object.getOwnPropertySymbols方法能够取到类里面声明的所有Symbol属性。下面是一个破坏Stack类的例子：

let stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length);     //1
console.log(objectSymbols);   //[Symbol()]
console.log(objectSymbols[0].push(1));
stack.print();   //5,8,1

// 2.用ES6的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);
        let r = s.pop();
        return r;
    }
    ...
}

现在items是真正的私有属性了，但还有一件事要做。items现在仍然是在Stack类以外声明的，因此谁都可以改动他。我们要用一个闭包把Stack类包起来，这样就只能在这个函数里访问WeakMap：

let Stack = (function() {
    const items = new WeakMap();
    class Stack{
        constructor() {
            items.set(this,[]);
        }
        ...}
    return Stack;
})();

然而用这种方法的话，扩展类无法继承私有属性。

用栈解决问题

从十进制到二进制

function dec2bin(decNumber) {
    let stack = new Stack()
    while (decNumber > 0 ) {
        stack.push(decNumber % 2)
        decNumber = Math.floor(decNumber / 2)
    }
    let binaryString = ''
    while(!stack.isEmpty()) {
        binaryString += stack.pop()
    }
    return binaryString
}
console.log(dec2bin(100));   //1100100