Javascript数据结构与算法（三）栈

栈是一种遵循后进先出（ILFO）原则的有序集合，新添加或待删除的元素都保存在栈的同一段，称为栈顶，另一端就叫栈底。现实中很多例子采用了这种数据结构，比如一摞书，叠放的盘子。栈通常用来保存变量、方法调用，当然也可以用于浏览器历史记录。

基于数组的栈

创建类

class StackArray {
  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;
  }

清空栈元素

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

转化为数组

toArray() {
    return this.items;
  }

转化为字符串

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

基于Javascript对象的stack类

创建stack类

class Stack {
  constructor() {
    this.count = 0;//记录栈的大小，帮助我们进行添加和删除操作
    this.items = {};
  }

添加元素

push(element) {
    this.items[this.count] = element;
    this.count++;
  }

删除元素

pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

验证一个栈是否为空和它的大小

isEmpty() {
    return this.count === 0;
  }

  size() {
    return this.count;
  }

查看栈顶的值并将栈清空

peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  };
clear() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    this.items = {};
    this.count = 0;
  };

转为字符串

toString() {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

总结

除了toString方法，我们创建的其他方法的时间复杂度均是O(1),代表我们可以直接扎到目标元素并对其进行操作。

注意

目前为止我们使用的是ES6语法类，由于JavaScript语言的特点，类并不能跟其他语言一样具有私有属性，也就是在外部可以引用私有属性，对其进行赋值等操作。看以下的代码了解一下：

const stack = new Stack();
console.log(Object.getOwnPropertyNames(stack));//["count","items"]
console.log(Object.keys(stack));//["count","items"]
console.log(stack.items);//直接访问私有属性

那么问题来了，我们只想让用户使用我们暴露出来的属性或者方法，我们该怎么实现私有属性呢。笔者看了前辈总结的，直接把它写上来。

保护数据结构内部元素

下划线命名约定

class stack{
    constructor(){
        this._count = 0;
        this._items = {};
    }
};

这只是一种约定，只能依赖于开发人员具备的常识

用E2015的限定作用于Symbol实现类

const _items = Symbol('stackItems');
class Stack{
    constructor(){
        this[_items] = [];
    }
};

实现了假的私有属性，虽然Symbol基本类型不可变，但由于ES2015新增的Object.getOwnPropertySymbols方法仍然能取到所有Symbol属性，而且是数组的形式，但我们操作的是栈，不应该出现这种行为。别急，还有第三个方案

用ES2015的WeakMap实现类

const items = new WeakMap();
class Stack{
    constructor(){
        items.set(this,[]);
    },
    push(element){
        const s = items.get(this);
        s.push(element);
    }
}

这样我们就实现了一个实现了一个完全的私有属性 ，但是代码可读性对于笔者真的太难受了，不知道你们怎么觉得呢。

栈的实践

进制转换算法

function baseConverter(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);
    number = Math.floor(number / base);
  }

  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()];
  }

平衡圆括号算法

function parenthesesChecker(symbols) {
  
const stack = new Stack();
  const opens = '([{';
  const closers = ')]}';
  let balanced = true;
  let index = 0;
  let symbol;
  let top;

  while (index < symbols.length && balanced) {
    symbol = symbols[index];
    if (opens.indexOf(symbol) >= 0) {
      stack.push(symbol);
    } else if (stack.isEmpty()) {
      balanced = false;
    } else {
      top = stack.pop();
      if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
        balanced = false;
      }
    }
    index++;
  }
  return balanced && stack.isEmpty();
}