栈是一种遵循从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端称作栈顶，另一端就叫栈底。

在栈里，新的元素都靠近栈顶，旧的元素都接近栈底。

生活中栈的例子：一摞书，叠放的盘子。

栈也被用在编程语言的编译器和内存中保存变量、方法调用等。也被用于浏览器历史记录（浏览器的返回按钮）。

创建一个基于数组的栈

  • 向栈添加元素
  • 从栈移除元素
  • 查看栈顶元素
  • 检查栈是否为空
  • 清空栈元素
  • 使用 Stack 类
  1. /**
  2.  * 创建一个基于数组的栈
  3.  */
  4. class Stack {
  6.   constructor() {
  7.     this.items = [];  // 选择一种数据结构（数组）来保存栈里的元素
  8.   }
  10.   // 添加一个（或几个）新元素到栈顶
  11.   push(element) {
  12.     this.items.push(element);
  13.   }
  15.   // 移除栈顶的元素，同时返回被移除的元素
  16.   pop() {
  17.     return this.items.pop();
  18.   }
  20.   // 返回栈顶的元素，但不对栈做任何修改
  21.   peek() {
  22.     return this.items[this.items.length - 1];
  23.   }
  25.   // 如果栈里没有元素就返回 true，否则返回 false
  26.   isEmpty() {
  27.     return this.items.length === 0;
  28.   }
  30.   // 返回栈里的元素个数
  31.   size() {
  32.     return this.items.length;
  33.   }
  35.   // 移除栈里的所有元素
  36.   clear() {
  37.     this.items = [];
  38.   }
  40. }
  1. /**
  2.  * 使用 Stack 类
  3.  */
  4. // 初始化 Stack 类
  5. const stack = new Stack();
  7. // 验证栈是否为空
  8. console.log(stack.isEmpty());   // true
  10. // 往栈里添加元素
  11. stack.push(2);
  12. stack.push(5);
  13. stack.push(8);
  15. // 查看栈顶的元素
  16. console.log(stack.peek());    // 8
  18. // 查看栈里的元素个数
  19. console.log(stack.size());    // 3
  21. // 验证栈是否为空
  22. console.log(stack.isEmpty());   // false
  24. // 移除栈里的元素
  25. console.log(stack.pop());       // 8
  26. console.log(stack.pop());       // 5
  28. // 移除栈里的所有元素
  29. stack.clear();
  31. // 验证栈是否为空
  32. console.log(stack.isEmpty());   // true
  33. console.log(stack.peek());      // undefined
  34. console.log(stack.size());      // 0

创建一个基于 JavaScript 对象的 Srack 类

比基于数组的栈迭代占用的时间更少。

  1. /**
  2.  * 创建一个基于数组的栈
  3.  */
  4. class Stack {
  6.   constructor() {
  7.     this.count = 0;
  8.     this.items = {};
  9.   }
  11.   // 向栈中插入元素
  12.   // 在 JavaScript 中，对象是一系列键值对的集合。使用 count 变量作为 items 对象的键名，插入的元素则是它的值
  13.   push(element) {
  14.     this.items[this.count] = element;
  15.     this.count++;
  16.   }
  18.   // 移除栈顶的元素，同时返回被移除的元素
  19.   pop() {
  20.     if (this.isEmpty()) {
  21.       return undefined;
  22.     }
  23.     this.count--;
  24.     const result = this.items[this.count];
  25.     delete this.items[this.count];
  26.     return result;
  27.   }
  29.   // 返回栈顶的元素，但不对栈做任何修改
  30.   peek() {
  31.     if (this.isEmpty()) {
  32.       return undefined;
  33.     }
  34.     return this.items[this.count - 1];
  35.   }
  37.   // 如果栈里没有元素就返回 true，否则返回 false
  38.   isEmpty() {
  39.     return this.count === 0;
  40.   }
  42.   // 返回栈里的元素个数
  43.   size() {
  44.     return this.count;
  45.   }
  47.   // 移除栈里的所有元素
  48.   clear() {
  49.     this.items = {};
  50.     this.count = 0
  51.     // while (!this.isEmpty()) {
  52.     //   this.pop();
  53.     // }
  54.   }
  56.   // 创建一个 toString 方法来打印出栈的内容
  57.   toString() {
  58.     if (this.isEmpty()) {
  59.       return '';
  60.     }
  61.     let objString = `${this.items[0]}`;
  62.     for (let i = 1; i < this.count; i++) {
  63.       objString = `${objString}, ${this.items[i]}`;
  64.     }
  65.     return objString;
  66.   }
  68. }
  1. /**
  2.  * 使用 Stack 类
  3.  */
  4. // 初始化 Stack 类
  5. const stack = new Stack();
  7. // 验证栈是否为空
  8. console.log(stack.isEmpty());   // true
  10. // 往栈里添加元素
  11. stack.push(2);
  12. stack.push(5);
  13. stack.push(8);
  15. // 打印栈的内容
  16. console.log(stack.toString());    // 2, 5, 8
  18. // 查看栈顶的元素
  19. console.log(stack.peek());        // 8
  21. // 查看栈里的元素个数
  22. console.log(stack.size());        // 3
  24. // 验证栈是否为空
  25. console.log(stack.isEmpty());     // false
  27. // 移除栈里的元素
  28. console.log(stack.pop());         // 8
  29. console.log(stack.pop());         // 5
  31. // 移除栈里的所有元素
  32. stack.clear();
  34. // 验证栈是否为空
  35. console.log(stack.isEmpty());   // true
  36. console.log(stack.peek());      // undefined
  37. console.log(stack.size());      // 0
  40. // 从下面行 {1} 和 行 {2} 得出：count 和 items 属性是公开的，我们可以像行 {3} 那样直接访问它们
  41. // 根据这种行为，可以对这两个属性赋新的值
  42. console.log(Object.getOwnPropertyNames(stack));   // [ 'count', 'items' ]
  43. console.log(Object.keys(stack));                  // [ 'count', 'items' ]
  44. console.log(stack.items);                         // {}

在 Stack 类声明的 items 和 count 属性并没有得到保护。ES6 类是基于原型的，基于原型的类能节省内存空间并在扩展方面优于函数的类，但这种方式不能声明私有属性（变量）或方法。我们希望 Stack 类的用户只能访问我们在类中暴露的方法。

保护数据结构内部元素

1. 下划线命名约定

  1. class Stack1 {
  2.   constructor() {
  3.     this._count = 0;
  4.     this._items = {};
  5.   }
  6.   // 栈的方法
  7. }

这种方式只是一种约定，并不能保护数据，而且只能依赖于使用该类的开发者所具备的常识。

2. 用 ES6 的限定作用域 Symbol 实现 Stack 类

  1. const _items = Symbol('stackItems');  // 声明 Symbol 类型的变量 _items
  2. class Stack2 {
  3.   constructor() {
  4.     this[_items] = [];                // 在类的构造函数中初始化它的值
  5.   }
  6.   // 栈的方法
  8.   // 向栈中插入元素
  9.   // 在 JavaScript 中，对象是一系列键值对的集合。使用 count 变量作为 items 对象的键名，插入的元素则是它的值
  10.   push(element) {
  11.     this[_items][this.count] = element;
  12.     this.count++;
  13.   }
  15.   // 移除栈顶的元素，同时返回被移除的元素
  16.   pop() {
  17.     if (this.isEmpty()) {
  18.       return undefined;
  19.     }
  20.     this.count--;
  21.     const result = this[_items][this.count];
  22.     delete this[_items][this.count];
  23.     return result;
  24.   }
  26.   // 返回栈顶的元素，但不对栈做任何修改
  27.   peek() {
  28.     if (this.isEmpty()) {
  29.       return undefined;
  30.     }
  31.     return this[_items][this.count - 1];
  32.   }
  34.   // 如果栈里没有元素就返回 true，否则返回 false
  35.   isEmpty() {
  36.     return this.count === 0;
  37.   }
  39.   // 返回栈里的元素个数
  40.   size() {
  41.     return this.count;
  42.   }
  44.   // 移除栈里的所有元素
  45.   clear() {
  46.     this[_items] = {};
  47.     this.count = 0
  48.     // while (!this.isEmpty()) {
  49.     //   this.pop();
  50.     // }
  51.   }
  53.   // 创建一个 toString 方法来打印出栈的内容
  54.   toString() {
  55.     if (this.isEmpty()) {
  56.       return '';
  57.     }
  58.     let objString = `${this[_items][0]}`;
  59.     for (let i = 1; i < this.count; i++) {
  60.       objString = `${objString}, ${this[_items][i]}`;
  61.     }
  62.     return objString;
  63.   }
  65. }
  67. const stack = new Stack2();
  68. stack.push(5);
  69. stack.push(8);
  70. let objectSymbols = Object.getOwnPropertySymbols(stack);
  71. console.log(objectSymbols.length);  // 1
  72. console.log(objectSymbols);         // [ Symbol(stackItems) ]
  73. console.log(objectSymbols[0]);      // Symbol(stackItems)
  74. stack[objectSymbols[0]].push(2);
  75. console.log(stack.toString());      // 2

这种方式创建了一个假的私有属性，因为 ES6 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbol 属性。

3. 用 ES6 的 WeakMap 实现 Stack 类

  1. const items = new WeakMap();      // 声明一个 WeakMap 类型的变量 items
  2. class Stack3 {
  3.   constructor() {
  4.     items.set(this, []);          // 以 this（Stack3 类自己的引用）为键，把代表栈的数组存入 items
  5.   }
  6.   push(element) {
  7.     const s = items.get(this);    // 从 WeakMap 中取出值，以 this 为键从 items 中取值
  8.     s.push(element);
  9.   }
  10.   pop() {
  11.     const s = items.get(this);
  12.     const r = s.pop();
  13.     return r;
  14.   }
  15.   // 栈的其他方法
  16. }

这种方式，items 在 Stack 类里是真正的私有属性。但代码可读性不强，而且在扩展该类时无法继承私有属性。鱼与熊掌不可兼得！

4. 通过在属性前添加 # 作为前缀来声明私有属性

  1. class Stack4 {
  2.   #count = 0;
  3.   #items = 0;
  4.   // 栈的方法
  5. }

用栈解决进制转换问题

  1. /**
  2.  * 创建一个基于数组的栈
  3.  */
  4. class Stack {
  6.   constructor() {
  7.     this.items = [];  // 选择一种数据结构（数组）来保存栈里的元素
  8.   }
  10.   // 添加一个（或几个）新元素到栈顶
  11.   push(element) {
  12.     this.items.push(element);
  13.   }
  15.   // 移除栈顶的元素，同时返回被移除的元素
  16.   pop() {
  17.     return this.items.pop();
  18.   }
  20.   // 返回栈顶的元素，但不对栈做任何修改
  21.   peek() {
  22.     return this.items[this.items.length - 1];
  23.   }
  25.   // 如果栈里没有元素就返回 true，否则返回 false
  26.   isEmpty() {
  27.     return this.items.length === 0;
  28.   }
  30.   // 返回栈里的元素个数
  31.   size() {
  32.     return this.items.length;
  33.   }
  35.   // 移除栈里的所有元素
  36.   clear() {
  37.     this.items = [];
  38.   }
  40. }
  • 十进制转二进制
  1. // 十进制转二进制
  2. function decimalToBinary(decNumber) {
  3.   const remStack = new Stack();
  4.   let number = decNumber;
  5.   let rem;
  6.   let binaryString = '';
  8.   while (number > 0) {
  9.     rem = Math.floor(number % 2);
  10.     remStack.push(rem);
  11.     number = Math.floor(number / 2);
  12.   }
  14.   while (!remStack.isEmpty()) {
  15.     binaryString += remStack.pop().toString();
  16.   }
  18.   return binaryString;
  19. }
  21. console.log(decimalToBinary(233));    // 11101001
  22. console.log(decimalToBinary(10));     // 1010
  23. console.log(decimalToBinary(1000));   // 1111101000
  • 进制转换算法
  1. // 进制转换算法
  2. function baseCnverter(decNumber, base) {
  3.   const remStack = new Stack();
  4.   const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  5.   let number = decNumber;
  6.   let rem;
  7.   let baseString = '';
  9.   if (!(base >= 2 && base <= 36)) {
  10.     return '';
  11.   }
  13.   while (number > 0) {
  14.     rem = Math.floor(number % base);
  15.     remStack.push(rem);
  16.     number = Math.floor(number / base);
  17.   }
  19.    while (!remStack.isEmpty()) {
  20.      baseString += digits[remStack.pop()];
  21.    }
  22.    return baseString;
  23. }
  25. console.log(baseCnverter(100345, 2));   // 11000011111111001
  26. console.log(baseCnverter(100345, 8));   // 303771
  27. console.log(baseCnverter(100345, 16));  // 187F9
  28. console.log(baseCnverter(100345, 35));  // 2BW0