JavaScript数据结构（一）栈

栈是一个后进先出的数据结构

JavaScript中没有栈，但可以用Array实现栈的所有功能

栈常见操作：push、pop、stack[stack. length-1]

1. 定义

后进先出，相当于往容器里放东西

用途：

编程语言的编译器和内存中保存变量、方法调用

浏览器历史记录（浏览器的返回按钮）

函数堆栈调用

……

2. 具体操作

创建

class Stack {
    constructor() {
        this.items = [];
    }
}
复制代码

方法：

• push(element(s))：添加一个（或几个）新元素到栈顶

  push(element) {
      this.items.push(element);
  }
  复制代码

• pop()：移除栈顶的元素，同时返回被移除的元素

  pop() {
  	return this.items.pop();
  }
  复制代码

• peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）

  peek() {  //查看栈里最后添加的元素是什么
  	return this.items[this.items.length - 1];
  }
  复制代码

• isEmpty()：如果栈里没有任何元素就返回true，否则返回false

  isEmpty() {  //判断内部数组的长度是否为0
  	return this.items.length === 0;
  }
  复制代码

• clear()：移除栈里的所有元素

  clear() {  //也可以多次调用pop方法，把数组中的元素全部移除
  	this.items = [];
  }
  复制代码

• size()：返回栈里的元素个数（和length 属性类似）

  size() {  //对于集合，最好使用size代替length
  	return this.items.length;
  }
  复制代码

3. 使用

const stack = new Stack();  //创建栈
console.log(stack.isEmpty());  //此时栈为空
stack.push(5);  //添加元素到栈顶
console.log(stack.peek());  //5 => 往栈里添加的最后一个元素为5
console.log(stack.size());    //1
console.log(stack.isEmpty());  //false
stack.push(8);
stack.push(11);
stack.pop(); 
stack.pop();  //调用两次，移除两个元素
console.log(stack.size());  //1
复制代码

4. 基于JavaScript对象的Stack类

最简单的方式：使用数组来存储其元素

基本结构：

class xxx {
 constructor() {
     //构造
	}
 //写方法
}
//调用
复制代码

5. 保护数据结构内部元素

使用 “_” “#” 前缀来声明私有属性，需要编写相应的代码逻辑

使用es6中的Symbol

使用es6中的WeakMap

const items = new WeakMap();

class Stack {
    construtor() {
        items.set(this, []);
    }
    push(element) {
        const s = items.get(this);
        s.push(element);
    }
    pop() {
        const s = items.get(this);
        const r = s.pop();
        return r;
    }
}
复制代码

6. 应用

十进制 –> 二进制

通过二进制的计算方法，可以知道二进制的结果是余数从高位到低位排列的

decimalToBinary = (decNumber) => {
    const remStack = new Stack();
    let number = decNumber;
    let rem;
    let binaryString = '';

    while (number > 0) {
        rem = Math.floor(number % 2);
        remStack.push(rem);
        number = Math.floor(number / 2);
    }

    while (!remStack.isEmpty()) {
        binaryString += remStack.pop().toString();
    }

    return binaryString;
}
复制代码

其他进制转换

function baseConverter(decNumber, base) {  //decNumber转换的数字，base几进制
    const remStack = new Stack();
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    let number = decNumber;
    let rem;
    let baseString = '';

    if (!(base >= 2 && base <= 36)) {
        return '';
    }

    while (number > 0) {
    rem = Math.floor(number % base);
    remStack.push(rem);   //往stack里添加元素
    number = Math.floor(number / base);
    }

    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()]; //从堆里面拿出元素
    }
    return baseString;
}

console.log(baseConverter(1111111, 3));
复制代码

函数的堆栈调用

const func1 = () => {
    func2();
}
const func2 = () => {
    func3();
}
const func3 = () => {}
复制代码

我们使用node进行debug：

可以看到，实际上，函数的调用也是满足后进先出的顺序

即，func3()最后进去，最先执行完的是func3()

一道LeetCode题

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const stack = [];
    for(let i = 0; i < s.length; i++) {
        const c = s[i];
        if(c === '(' || c=== '{' || c === '[') {
            stack.push(c);
        } else {
            const t = stack[stack.length - 1]; //栈顶元素
            if(
                (t === '(' && c ===  ')') ||
                (t === '{' && c ===  '}') ||
                (t === '[' && c ===  ']') 
            ) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.length === 0;
};
复制代码