栈和队列类似于数组，但在添加和删除元素时更为可控。

1. 栈数据结构

栈是一种遵从后进先出（LIFO）原则的有序集合，两端分别是栈顶和栈底。新添加的或者待删除的元素都保存在栈顶。编译器和内存中保存变量、方法调用等都会用到栈。

1.1 创建栈

• push(element(s))：添加一个（或几个）新元素到栈顶。
• pop()：移除栈顶的元素，同时返回被移除的元素。
• peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
• isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
• clear()：移除栈里的所有元素。

• size()：返回栈里的元素个数。这个方法和数组的length属性很类似。

  1.1.1 传统方式

  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());
  };
  }

  1.1.2 ES6 Class

  使用了 WeakMap，键是对象，值是任意数据类型。WeakMap 对比 Map 而言（WeakSet 同理）：

• 没有 entries、keys、values 等迭代器方法；

• 只能用对象作为键。

这里键是 this，值是数组。从而每个实例都可以根据自己的 this 获取私有的数组池。除非知道别的实例 this，否则也不会取出别的实例中的值（因为没有迭代器方法）。

const Stack = (function () {
  const items = new WeakMap();
  class Stack {
    constructor() {
      items.set(this, []);
    }
    push(element) {
      const s = items.get(this);
      s.push(element);
    }
    pop() {
      const s = items.get(this);
      return s.pop();
    }
    peek() {
      const s = items.get(this);
      return s[s.length - 1];
    }
    isEmpty() {
      const s = items.get(this);
      return s.length === 0;
    }
    size() {
      const s = items.get(this);
      return s.length;
    }
    clear() {
      items.set(this, []);
    }
    print() {
      const s = items.get(this);
      console.log(s.toString());
    }
  }
  return Stack;
})();

2. 栈相关问题

据说栈有三个著名的算法场景：

• 十进制转二进制
• 平衡圆括号

• 汉诺塔问题

  2.1 十进制转二进制

  ```javascript /**

  • 十进制数字和2整除，直至结果是0，然后反向输出余数，得到转换后的二进制 */ function convert10To2(decNumber) { let remStack = new Stack(), rem, binaryString = ‘’;

  while (decNumber > 0) { rem = decNumber % 2; remStack.push(rem); decNumber = Math.floor(decNumber / 2); }

  while (!remStack.isEmpty()) { binaryString += remStack.pop().toString(); }

  return binaryString; }

const test = 15; const result = convert10To2(test); console.log(result); console.log(‘测试转换结果是否正确：’, result === test.toString(2));

<a name="KeIG6"></a>
## 2.2 任意进制转十进制
```javascript
/**
 * 任意进制转十进制(十六进制及以内）
 */
function baseConverter(decNumber, base) {
  let remStack = new Stack(),
    rem,
    baseString = '',
    digits = '0123456789ABCDEF';
  while (decNumber > 0) {
    rem = decNumber % base;
    remStack.push(rem);
    decNumber = Math.floor(decNumber / base);
  }
  while (!remStack.isEmpty()) {
    baseString += digits[remStack.pop()];
  }
  return baseString;
}
const test2 = 2501234;
const result2 = baseConverter(test2, 16);
console.log(result2);
console.log('测试转换结果是否正确：', result2 === test2.toString(16).toUpperCase());

2.3 判断括号是否平衡

// https://leetcode.com/problems/valid-parentheses/
/**
 * 判断括号是否匹配
 *
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  if (s.length === 0) return true;
  const stack = [];
  // 遇见左括号就入栈，右括号就弹出栈顶进行匹配
  // 平衡多少对儿，就弹出多少个左括号
  // 若能全部平衡，则最后栈应为空
  const dict = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  const isLeft = (c) => '({['.includes(c);
  if (!isLeft(s[0])) return false;
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (isLeft(c)) {
      stack.push(c);
    } else {
      if (dict[c] !== stack.pop()) {
        return false;
      }
    }
  }
  return stack.length === 0;
};