1. 数据结构-栈

​ 在 js 中,栈更像是一种变种的数组,只是没有数组那么多方法,也就没有数组那么灵活.但是栈和队列这两种数据结构比数组更加的高效和可控.而在 js 中模拟栈,依据的主要形式也是数组.

栈(stack)是一种遵循后进先出(Last In First Out)原则的有序集合.新添加的元素和待删除的元素都保存在栈的同一端,称为栈顶,另一端就叫做栈底.在栈里,新元素都接近栈顶,旧元素都靠近栈底.其实可以把栈简单的理解成往一个木桶里堆叠的放入物品,最后放进去的在桶的顶端,也是可以最先拿出来的,而最先放进去的却在桶的底部,只有把上面的物品拿出来之后才可以拿走底部的物品.

对于数组来说,可以添加元素,删除元素,获取数组的长度以及返回对应下标所对应的值,那么在构造一个栈之前,我们需要了解一下栈都有哪些基本操作.

1. 压栈,也称之为入栈,也就是把元素加入栈中.就像是数组中的 push 一样.
2. 出栈,移除位于栈顶的元素.就像是数组的 pop 一样.
3. 获取栈顶的元素,不对栈进行任何操作,就像是数组中通过下标获取对应的值一样.
4. 判断栈是否为空.就像是在数组中判断数组的长度是否为 0 一样.
5. 清空栈,也就是移除栈里面的所有元素.就像是把数组的长度设置为 0 一样.
6. 获取栈里的元素个数,就像是数组中的 length 属性一样.

构造函数实现栈

function Stack() {
  let items = [];

  // 首先,我们来实现一个入栈的方法,这个方法负责往栈里加入元素,要注意的是,该方法只能添加元素到栈顶
  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 items.length;
  };

  //清空栈
  this.clear = function () {
    items = [];
  };

  //打印栈内元素
  this.print = function () {
    console.log(items.toString());
  };
}

/*
let stack = new Stack();
console.log(stack.isEmpty());//true
stack.push(1);
stack.print();
stack.push(3);
stack.print();
console.log(stack.isEmpty());//false
console.log(stack.size());//2
stack.push(10);
stack.print();
stack.pop();
stack.print();
stack.clear();
console.log(stack.isEmpty());//true
*/

Class 实现栈

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 = [];
  }

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

  print() {
    console.log(this.items.toString());
  }
}

Symbol 实现栈

const _items = Symbol("stackItems");

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] = [];
  }

  print() {
    console.log(this.toString());
  }

  toString() {
    return this[_items].toString();
  }
}

WeakMap 实现栈

//通过闭包把声明的变量变成私有属性
let Stack = (function () {
  //声明栈的基本依赖
  const _items = new WeakMap();
  //声明计数器,因为WeakMap是键值对的'对象类型',本身是没有像数组这样的长度只说的
  const _count = new WeakMap();

  class Stack {
    constructor() {
      //初始化stack和计数器的值，这里的set是WeakMap的自身方法，通过set和get来设置值和取值，这里用this作为设置值的键名，那this又指向啥呢？自行console！
      _count.set(this, 0);
      _items.set(this, {});
    }

    push(element) {
      //在入栈之前先获取长度和栈本身
      const items = _items.get(this);
      const count = _count.get(this);
      //这里要注意_count可是从0开始的噢
      items[count] = element;
      _count.set(this, count + 1);
    }

    pop() {
      //如果为空，那么则无法出栈
      if (this.isEmpty()) {
        return undefined;
      }
      //获取items和count，使长度减少1
      const items = _items.get(this);
      let count = _count.get(this);
      count--;
      //重新为_count赋值
      _count.set(this, count);
      //删除出栈的元素，并返回该元素
      const result = items[count];
      delete items[count];
      return result;
    }

    peek() {
      if (this.isEmpty()) {
        return undefined;
      }
      const items = _items.get(this);
      const count = _count.get(this);
      //返回栈顶元素
      return items[count - 1];
    }

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

    size() {
      return _count.get(this);
    }

    clear() {
      /* while (!this.isEmpty()) {
            this.pop();
          } */
      _count.set(this, 0);
      _items.set(this, {});
    }

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

    print() {
      console.log(this.toString());
    }
  }

  return Stack;
})();

const stack = new Stack();
stack.push(1);
stack.push(3);
stack.print(); // 1, 3, 1