数组是一种灵活自由的线性结构，栈是一种受限的线性结构。
限制：只允许在一端进行操作，这端为栈顶，另一端为栈底。
实现栈结构一般有基于数组和基于链表两种方式。

函数调用栈

A调用B，B调用C，C调用D。
A最先被压入栈，D最后被压入栈，D执行完后弹出栈，以此类推，A最后出栈。
函数调用栈的称呼由函数调用的执行机制而来。

递归容易出现栈溢出。

创建一个基于数组的栈

使用数组来保存栈的元素，但由于栈的LIFO，需要对元素的插入和删除进行限制。

  1.  push(element(s)):添加一个(或几个)新元素到栈顶。
  2.  pop():移除栈顶的元素，同时返回被移除的元素。
  3.  peek():返回栈顶的元素，不对栈做任何修改(该方法不会移除栈顶的元素，仅仅返回它)。
  4.  isEmpty():如果栈里没有任何元素就返回 true，否则返回 false。
  5.  clear():移除栈里的所有元素。
  6.  size():返回栈里的元素个数。该方法和数组的 length 属性很类似。
  8. class Stack {
  9.   constructor() {
  10.     this.item = [];
  11.   }
  13.   push(ele) {
  14.     this.item.push(ele);
  15.   }
  17.   pop() {
  18.     return this.item.pop();
  19.   }
  21.   peek() {
  22.     return this.item[item.length - 1];
  23.   }
  25.   isEmpty() {
  26.     // return !this.item.length;
  27.     return this.item.length === 0;
  28.   }
  30.   clear() {
  31.     this.item = []
  32.   }
  34.   size() {
  35.     return this.item.length;
  36.   }
  37. }

使用Stack类

  1. const stack = new Stack();
  2. console.log(stack.isEmpty()); // true
  4. stack.push(5);
  5. stack.push(8);
  6. console.log(stack.peek()); // 8
  7. console.log(stack.size()); // 2
  8. stack.pop();
  9. console.log(stack.size()); // 1

创建一个基于JavaScript对象的栈

使用数组在查找元素时大部分方法的时间复杂度是O(n)，O(n)的意思是需要迭代整个数组直到找到那个元素。
使用对象来存储元素，可以占用较少的内存空间。
下列方法中除了toString() 方法，其他方法复杂度为O(1)。

  1. class Stack {
  2.   constructor() {
  3.     this.item = {};
  4.     this.count = 0;
  5.   }
  7.   push(ele) {
  8.     this.count += 1;
  9.     this.item[this.count] = ele;
  10.   }
  12.   pop() {
  13.     if(this.isEmpty()) {
  14.       return undefined;
  15.     }
  16.     const res = this.item[this.count];
  17.     delete this.item[this.count];
  18.     this.count -= 1;
  19.     return res;
  20.   }
  22.   peek() {
  23.     if(this.isEmpty()) {
  24.       return undefined;
  25.     }
  26.     return this.item[this.count];
  27.   }
  29.   isEmpty() {
  30.     return !this.count;
  31.   }
  33.   clear() {
  34.     this.item = {};
  35.     this.count = 0;
  37.     // clear的另一种写法
  38.     while(!this.isEmpty()) {
  39.       this.pop();
  40.     }
  41.   }
  43.   size() {
  44.     return this.count;
  45.   }
  47.   // 基于数组的栈自带toString()方法，此处应手动添加。
  48.   toString() {
  49.     let str = "";
  50.     if (this.isEmpty()) return str;
  51.     for (const k in this.item) {
  52.       str = str ? `${str},${this.item[k]}` : this.item[k];
  53.     }
  54.     return str;
  55.   }
  56. }

保护数据结构内部元素

在上述创建栈的方法中，我们发现，item和count能被直接访问到。

  1. console.log(Object.getOwnPropertyNames(stack)); // [ 'item', 'count' ]
  2. console.log(Object.keys(stack)); // [ 'item', 'count' ]
  3. console.log(stack.item); // { '1': 5, '2': 8, '3': 5, '4': 8 }

下划线命名的约定

  1. class Stack {
  2.   constructor() {
  3.     // 约定下划线来标记私有属性
  4.     this._count = 0;
  5.     this._items = {};
  6. } }

ES6: WeakMap实现类

  1. const items = new WeakMap(); // {1}
  2.   class Stack {
  3.     constructor () {
  4.   items.set(this, []); // {2}
  5.     }
  6.     push(element){
  7.   const s = items.get(this); // {3}
  8.   s.push(element); }
  9.     pop(){
  10.       const s =
  11.       const r =
  12.       return r;
  13.   }
  14. // 其他方法
  15. }
  16. items.get(this); s.pop();
  17. 上面的代码片段解释如下。
  18.  行{1}，声明一个 WeakMap 类型的变量 items。
  19.  行{2}，在 constructor 中，以 this(Stack 类自己的引用)为键，把代表栈的数组存入 items。
  20.  行{3}，从 WeakMap 中取出值，即以 this 为键(行{2}设置的)从 items 中取值。

TS: private修饰符

TypeScript 提供了一个给类属性和方法使用的 private 修饰符。然而，该修饰符只在编译时有用(包括我们在前几章讨论的 TypeScript 类型和错误检测)。在代码被转移完成后，属性同样是公开的。

用栈解决问题

十进制转二进制

  1. function decimalToBinary(decNumber) {
  2.   const remStack = new Stack();
  3.   let number = decNumber;
  4.   let rem;
  5.   let binaryString = "";
  6.   while (number > 0) {
  7.     // {1}
  8.     rem = Math.floor(number % 2); // {2}
  9.     remStack.push(rem); // {3}
  10.     number = Math.floor(number / 2); // {4}
  11.   }
  12.   while (!remStack.isEmpty()) {
  13.     // {5}
  14.     binaryString += remStack.pop().toString();
  15.   }
  16.   return binaryString;
  17. }
  18. console.log(decimalToBinary(233)); // 11101001
  19. console.log(decimalToBinary(10)); // 1010
  20. console.log(decimalToBinary(1000)); // 1111101000

进制转换算法

  1. function baseConverter(decNumber, base) {
  2.   const remStack = new Stack();
  3.   const digits = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // {6}
  4.   let number = decNumber;
  5.   let rem;
  6.   let baseString = "";
  7.   if (!(base >= 2 && base <= 36)) {
  8.     return "";
  9.   }
  10.   while (number > 0) {
  11.     rem = Math.floor(number % base);
  12.     remStack.push(rem);
  13.     number = Math.floor(number / base);
  14.   }
  15.   while (!remStack.isEmpty()) {
  16.     baseString += digits[remStack.pop()]; // {7}
  17.   }
  18.   return baseString;
  19. }
  20. console.log(baseConverter(100345, 2)); // 11000011111111001
  21. console.log(baseConverter(100345, 8)); // 303771 6
  22. console.log(baseConverter(100345, 16)); // 187F9
  23. console.log(baseConverter(100345, 35)); // 2BW0