数据结构 - 栈

一目录

不折腾的前端，和咸鱼有什么区别

目录
一目录
二前言
三模拟实现栈
四进制转换算法
4.1 十进制转二进制
4.2 十进制和十六以内任意进制转换
五平衡圆括号
六总结

二前言

经典开局：什么是栈？

栈是一种遵从后进先出（LIFO）原则的有序集合。

没听懂？举个例子：

有一摞书，先放的在最底下，在书非常多的情况你拿不到底部的书的情况下，如果你要拿到最底下的书，你每次需要先将最后放的先挪开，最后才能拿到最底下的书。
厨房堆放的盘子，每次拿的是最上面的，最后才拿底层（最先叠的）。

看到这里，相信小伙伴们会联想起两个数组的方法：push()、pop()。

是的，假设有一个数组：

const arr = [1, 2, 3, 4];

如果我们需要往里面进行堆栈行为，那么就是通过 arr.push() 往里面添加元素，通过 arr.pop() 往外推出元素。

当然，模拟栈还不止这些方法，我们继续往下瞧~

三模拟实现栈

首先，为栈声明一些方法：

push(element)：添加一个或者多个元素到栈顶
pop()：移除栈顶的元素，同时返回该元素
peek()：查看栈顶的元素
isEmpty()：判断栈是否空了，是则返回 true，否则返回 false
clear()：清除栈中的所有元素
size：返回栈里的元素个数，方法和 length 类似

然后，我们尝试实现这些方法：

function Stack() {
  let items = [];
  this.push = function(element) {
    items.push(element);
  };
  this.pop = function() {
    const pop = items.pop();
    return pop;
  };
  this.peek = function() {
    return items[items.length - 1];
  };
  this.isEmpty = function() {
    return items.length === 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size = function() {
    return items.length;
  };
}

let stack = new Stack();
stack.push(1);
// stack: [1]

stack.pop();
// stack: []

stack.push(1);
stack.push(2);
// stack: [1, 2]

stack.peek();
// Console: 2

stack.isEmpty();
// Console: false

stack.clear();
// stack: []

stack.size();
// 0

当然，如果纯粹看 jsliang 写的，没图没视频，小伙伴们很容易懵逼，这里 jsliang 建议看各个大佬的文章或者通过下面章节的几个案例进一步了解：

四进制转换算法

如果小伙伴大学走过流程，应该会碰到个老教授，跟你讲十进制转二进制。

如果小伙伴还没听过，那么 jsliang 来介绍一下~

4.1 十进制转二进制

10 进制转换成 2 进制，是怎么走的呢？

10 进制的 10 转 2 进制

10 % 2 = 0 | 10 / 2 = 5
 5 % 2 = 1 |  5 / 2 = 2
 2 % 2 = 0 |  2 / 2 = 1
 1 % 2 = 1 |  1 / 2 = 0

在这里，10 进制的 10 转换成 2 进制变成 1010。

10 进制的 25 转 2 进制

25 % 2 = 1 | 25 / 2 = 12
12 % 2 = 0 | 12 / 2 = 6
 6 % 2 = 0 |  6 / 2 = 3
 3 % 2 = 1 |  3 / 2 = 1
 1 % 2 = 1 |  1 / 2 = 0

在这里，10 进制的 25 转换成 2 进制变成 11001。

那么，下面开始解密：

已知 10 进制的数为 n。
将 n 每次取余 2 的值放入栈底部。
将 n 每次除于 2 的值当成下一次循环的数字（向下取整，舍弃小数部位）。
循环步骤 2 和步骤 3，直至 n 等于 0 为止。
将栈的数值依序推出来，从而得到最终结果。

说这么多，且看代码：

const decimalToBinary = (num) => {
  const result = [];
  while (num > 0) {
    result.push(num % 2);
    num = Math.floor(num / 2);
  }
  return result.reverse().join('');
};

console.log(decimalToBinary(10)); // '1010'
console.log(decimalToBinary(25)); // '11001'

怎么样，是不是感觉 So easy~

当然，为了防止看不懂，咱们还可以再修改修改：

const decimalToBinary = (num) => {
  const stack = [];
  let result = '';
  while (num > 0) {
    stack.push(num % 2);
    num = Math.floor(num / 2);
  }
  for (let i = stack.length - 1; i >= 0; i--) {
    result += stack[i];
  }
  return result;
};

console.log(decimalToBinary(10)); // '1010'
console.log(decimalToBinary(25)); // '11001'

这样，我们就完成了十进制转二进制啦~

4.2 十进制和十六以内任意进制转换

那么，既然这个这么好用，我们能不能改改，变成十进制转换成十六进制以内任意进制呢？

答案是可以的，上代码：

/**
 * @name 任意进制转换
 * @param {Number} number 需要转换的数字
 * @param {Number} binarySystem 需要转换成的进制
 */
const arbitraryBaseConversion = (number, binarySystem) => {
  const stack = [];
  const digits = '0123456789ABCDEF';
  while (number > 0) {
    stack.push(digits[Math.floor(number % binarySystem)]);
    number = Math.floor(number / binarySystem);
  }
  return stack.reverse().join('');
}

console.log(arbitraryBaseConversion(10, 2)); // '1010'
console.log(arbitraryBaseConversion(100, 2)); // '1100100'
console.log(arbitraryBaseConversion(10, 16)); // 'A'
console.log(arbitraryBaseConversion(100, 16)); // '64'

这样，我们就完成了十进制转十六进制内任意进制的方法啦~

五平衡圆括号

下面我们再尝试一下平衡圆括号的问题：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

如果小伙伴们希望能自己尝试一下，可以拿下面的代码试用：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    
};

用栈的话，怎么实现呢？

/**
 * @name 平衡圆括号
 * @param {string} s
 * @return {boolean}
 */
const isValid = (s) => {
  const stack = [];
  for (let i = 0; i < s.length; i++) {
    if (
      (s[i] === ')' && stack[stack.length - 1] === '(')
      || (s[i] === ']' && stack[stack.length - 1] === '[')
      || (s[i] === '}' && stack[stack.length - 1] === '{')
    ) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }
  console.log(stack);
  return stack.length === 0;
};

console.log(isValid('()'));     // true
console.log(isValid('()[]{}')); // true
console.log(isValid('(]'));     // false
console.log(isValid('([)]'));   // false
console.log(isValid('{[]}'));   // true

拿 ()[]{} 举例：

判断 ( 不是闭合括号，所以推入栈，stack = [ '(' ]；
判断 ) 是闭合括号，所以推出栈，stack = []；
判断 [ 不是闭合括号，所以推入栈，stack = [ '[' ]；
判断 ] 是闭合括号，所以推出栈，stack = []；
判断 { 不是闭合括号，所以推入栈，stack = [ '{' ];
判断 } 是闭合括号，所以推出栈，stack = []；

最后 stack.length 为 0 了，所以它是 true 的。

再拿 ([)] 举例：

判断 ( 不是闭合括号，所以推入栈，stack = [ '(' ]；
判断 [ 不是闭合括号，所以推入栈，stack = [ '(', '[' ]；
判断 ) 是闭合括号，但是栈顶层的元素是 [ 而不是 (，所以还是推入栈，stack = [ '(', '[', ')' ]；
判断 ] 是闭合括号，但是栈顶层的元素是 ) 而不是 [，所以还是推入栈，stack = [ '(', '[', ')', ']' ]；

最后 stack.length 为 4 了，所以它是 false 的。

这样，我们通过平衡圆括号进一步了解了栈的一些形式。

六总结

经过 进制转换 以及 平衡圆括号 这两道题目，想必小伙伴们应该对栈有了更深层次的了解。

当然，我们还有一些问题没有解决，例如：汉诺塔 等等，但是因为 jsliang 一时没有找到对应的题目（只有汉诺塔描述），所以这里就不哆嗦啦，下次碰到咱们再加上这里来。

不折腾的前端，和咸鱼有什么区别！

jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。

浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！

扫描上方二维码，关注 jsliang 的公众号（左）和 浪子神剑 的公众号（右），让我们一起折腾！