栈是一种遵从后进先出 LIFO 原则的有序集合。
新添加或待删除的元素都保存在栈顶，另一端叫栈底。
新元素靠近栈顶，旧元素接近栈底。

栈用在编译器和内存中保存变量、方法调用。

栈的方法

  • push(element) 添加元素到栈顶
  • pop() 移除栈顶元素，返回被移除元素
  • peek() 返回栈顶元素
  • isEmpty() 是否空栈
  • clear() 移除栈中所有元素

  • size() 返回栈的元素个数

    实现

    基于数组实现

    1. class Stack {
    2. constructor() {
    3.   this.items = [];
    4. }
    6. push(element) {
    7.   this.items.push(element);
    8. }
    10. pop() {
    11.   return this.items.pop();
    12. }
    14. peek() {
    15.   return this.items[this.items.length - 1];
    16. }
    18. isEmpty() {
    19.   return this.items.length === 0;
    20. }
    22. clear() {
    23.   this.items = [];
    24. }
    26. size() {
    27.   return this.items.length;
    28. }
    30. toString() {
    31.   return this.items.toString();
    32. }
    33. }

    基于对象实现

    1. class Stack {
    2. constructor() {
    3.   this._count = 0;
    4.   this._items = {};
    5. }
    7. push(element) {
    8.   this._items[this._count] = element;
    9.   this._count++;
    10. }
    12. pop() {
    13.   if (this.isEmpty()) {
    14.     return undefined;
    15.   }
    16.   this._count--;
    17.   const result = this._items[this._count];
    18.   delete this._items[this._count];
    19.   return result;
    20. }
    22. peek() {
    23.   if (this.isEmpty()) {
    24.     return undefined;
    25.   }
    26.   return this._items[this._count - 1];
    27. }
    29. isEmpty() {
    30.   return this._count === 0;
    31. }
    33. clear() {
    34.   this._items = {};
    35.   this._count = 0;
    36. }
    38. size() {
    39.   return this._count;
    40. }
    42. toString() {
    43.   if (this.isEmpty()) {
    44.     return '';
    45.   }
    46.   let objString = `${this._items[0]}`;
    47.   for (let i = 1; i < this._count; i++) {
    48.     objString = `${objString}, ${this._items[i]}`;
    49.   }
    50.   return objString;
    51. }
    52. }

    私有成员

    使 _ 真正不能访问

  1. Symbol ，使用 Object.getOwnPropertySymbols() 可被破

  2. WeakMap

    1. const Stack = (function () {
    2. const _items = new WeakMap();
    3. return class Stack{
    4.  constructor() {
    5.    _items.set(this, []);
    6.  }
    8.  push(element) {
    9.    _items.get(this).push(element);
    10.  }
    12.  pop() {
    13.    return _items.get(this).pop();
    14.  }
    16.  peek() {
    17.    return _items.get(this)[_items.get(this).length - 1];
    18.  }
    20.  isEmpty() {
    21.    return _items.get(this).length === 0;
    22.  }
    24.  clear() {
    25.    _items.get(this) = [];
    26.  }
    28.  size() {
    29.    return _items.get(this).length;
    30.  }
    32.  toString() {
    33.    return _items.get(this).toString();
    34.  }
    35. }
    36. })();