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

1. 栈数据结构

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

image.png

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 十进制转二进制

image.png

/**
 * 十进制数字和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));

2.2 任意进制转十进制

/**
 * 任意进制转十进制(十六进制及以内）
 */
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;
};