Javascript数据结构详解-栈

一、概念（Stack）

栈一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数 据。栈就像是一摞书，拿到新书时我们会把它放在书堆的最上面，取书时也只能从最上面的新 书开始取。

二、特点

• LIFO(Last In First Out),即最后添加的数据最先被取出
• 线性结构排列

三、Javascript简单实现

首先，列出一个栈应该具备的基本方法：

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

直接上ES6代码：

class Stack{
  constructor(){
    this.items = [];
  }
  push(item){
    this.items.push(item);
  }
  pop(){
    return this.items.pop();
  }
  peek(){
    return this.items.length ? this.items[this.items.length - 1] : undefined;
  }
  isEmpty(){
    return items.length === 0;
  }
  clear(){
    this.items = [];
  }
  size(){
    return this.items.length;
  }
}

四、思考和优化

如果你觉得上述代码就能实现一个Stack类？naive！ 来看如下代码：

 let stack = new Stack();
 stack.push(1);
 stack.push(2);
 stack.items;

结果输出 Stack: (2) [1, 2]

也就是说，我们应该每次只能通过peek、push、pop等方法来操作获取栈的信息。 这么直接stack.items访问很明显是不合理的。所以应该把items属性设置为私有的才行。

思路如下：

• 1、将items 从constructor中移除
• 2、用闭包，保证items在被引用的同时不被回收，即用私有变量取代类中属性

直接上代码：

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

       push(item){
          let s = items.get(this);
          s.push(item);
        }
        pop(){
          let s = items.get(this);
          return s.pop();
        }
        peek(){
          let s = items.get(this);
          return s.length ? s[s.length - 1] : undefined;
        }
        isEmpty(){
          let s = items.get(this);
          return s.length === 0;
        }
        clear(){
          let s = items.get(this);
          s = [];
        }
        size(){
          let s = items.get(this);
          return s.length;
        }
    }
    return Stack;
})();

这样，就可以避免通过实例来访问栈的私有属性了。

顺便再提一下，为什么要用到WeakMap:

也即是说，我们把一个数组，放到WeakMap中，不可枚举，遍历不到，这就达到了私有变量的效果了。

五、栈的实际应用

1、进制转换

10进制8转化为2进制数

function conver(num, radix) {
  let stack = new Stack()
  let binaryString = ''
  let digits = '0123456789ABCDEF'
  while (num > 0) {
    stack.push(num % radix)
    num = parseInt(num / radix)
  }
  while (!stack.isEmpty()) {
    binaryString += digits[stack.pop()]
  }
  console.log(binaryString)
}
conver(8, 2) // 输出：1000

2~9之间的通用的进制转换

 const convertHex = (num, base) => {
    var stack = new Stack();
    while (num > 0) {
        stack.push(num % base);
        num = Math.floor(num / base);
    }
    let converted = "";
    while (stack.length() > 0) {
        converted += stack.pop();
    }
    return converted;
}

2、判断是否是回文

const isPalindrome = (str) => {
    var stack = new Stack();
    str += ''; // 转换为字符串
    for (let i = 0, i< str.length; i++) {
        stack.push(str[i]);
    }
    let reverseWord = "";
    while (stack.size() > 0) {
        reverseWord += stack.pop();
    }
    return str === reverseWord;
}

3、有效的括号

思路如下：

• 1、碰到左括号，压入栈中
• 2、碰到右括号，直接将原来栈顶的元素给pop出来。
• 3、如果最终栈的元素为空，说明压入到栈的左括号都有遇到正确的闭合的右括号，被pop出来了。反之，则说明栈里面没有正确的闭合，或者一开始就先压入右括号。

const isValid = str => {
      const stack = new Stack();
      for(let i = 0;i<str.length;i++){
          if(str[i] === '(' || str[i] === '[' || str[i] === '{'){
              stack.push(str[i]);
          }else if((str[i] === ')' || str[i] === ']' || str[i] === '}')
          ){
              stack.size() && stack.pop();
          }
      }
      return stack.size() === 0;

   }

六、结语

要想在互联网的浩浩人海中卷出优势，必须得学好算法。 要想学好算法，得先了解基本的数据结构。 一点点的进步，今天先学好Stack栈。