栈

一.栈数据结构，生活中有什么例子?

1. 栈的特点。

   栈是一种遵从后进先出(LIFO)原则的有序集合，新增加和待删除的元素都会保存在栈的同一端， 叫做栈顶，另一端叫做栈底。

2. 生活中的例子。

   一桶薯片，最上面的最后放进去，吃的时候先拿上面的。

二、请实现一个栈，并实现以下方法：

• push(element)：添加一个新元素到栈顶。
• pop()：移除栈顶的元素，同时返回被移除的元素。
• peek()：返回栈顶的元素，不对栈做任何修改 (这个方法不会移除栈顶的元素，仅仅返回它)。
• isEmpty()：如果栈没有任何元素就返回 true，否则返回 false。
• clear()：移除栈里面的所有元素。
• size()：返回栈里的元素个数。这个方法与数组的 length 属性类似。

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

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

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

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

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

  size() {
    return this.items.length;
  }

  clear() {
    //this.items.length = 0;
    this.items = [];
  }
}

如果想清空一个数组，也可以设置length属性为0。

WeakMap只接受对象作为键名，不接受其他类型的值作为键名。键名是对象的弱引用，当对象被回收后，WeakMap自动移除对应的键值对，WeakMap结构有助于防止内存泄漏。

var wm = new WeakMap(); 
var obj = new Object(); 
wm.set(obj,'对象1'); 
obj=null; 
wm.get(obj);    //undefined 
wm.has(obj);    //false

使用WeakMap实现一个栈

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

        push(element) {
            item.get(this).push(element);
        }

        pop() {
            return item.get(this).pop();
        }

        peek() {
            return item.get(this)[item.get(this).length - 1];
        }

        isEmpty() {
            return item.get(this).length === 0;
        }

        size() {
            return item.get(this).length;
        }

        clear() {
            //this.item.length = 0;
            item.set(this, []);
        }
    }
    return Stack;
})()

那么这样有什么好处呢，主要是让item成为一个私有属性，外部无法进行访问和修改。

三、编写一个函数，实现十进制转换为二进制。

示例：

bitset(10)   --> "1010"
bitset(100)  --> "1100100"
bitset(1000) --> "1111101000"

使用栈来实现

实现：

function bitset(num) {
    if (!/^[1-9]+[0-9]*$/.test(num)) throw new TypeError('num is not a number, or a number starting with 0');
    let stack = new Stack();
    let bit = "";
    while (num) {
        stack.push(num % 2);
        num = Math.floor(num / 2);
    }
    while (!stack.isEmpty()) {
        bit += stack.pop().toString();
    }
    return bit;
}

四、编写一个函数，该函数接受一个括号字符串，并确定括号的顺序是否有效。如果字符串有效，函数应返回 true；如果字符串无效，则返回 false。

示例：

validParentheses("()" )             --> true
validParentheses(")(()))")          -->  false
validParentheses("(")               --> false
validParentheses("(())((()())())")  -->  true

使用栈来实现

实现思路：先匹配掉开始和结尾不是(和)的，并且其中不是由()组成的，

实现：

function validParentheses(str) {
    if (!/^\([\(|\)]*\)$/.test(str)) return false;
    let stack = new Stack();
    let arr = [...str];
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        if (arr[i] == '(') {
            stack.push(arr[i]);
        } else {
            if (stack.pop() !== '(') break;
        }
    }
    return stack.isEmpty();
}