阅读 450

数据结构 - 栈

一 目录

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

目录
一 目录
二 前言
三 模拟实现栈
四 进制转换算法
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

那么,下面开始解密:

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

说这么多,且看代码:

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'
复制代码

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

五 平衡圆括号

返回目录

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

leetcode-cn.com/problems/va…

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

有效字符串需满足:

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

示例 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
复制代码

案例 1

()[]{} 举例:

  1. 判断 ( 不是闭合括号,所以推入栈,stack = [ '(' ]
  2. 判断 ) 是闭合括号,所以推出栈,stack = []
  3. 判断 [ 不是闭合括号,所以推入栈,stack = [ '[' ]
  4. 判断 ] 是闭合括号,所以推出栈,stack = []
  5. 判断 { 不是闭合括号,所以推入栈,stack = [ '{' ];
  6. 判断 } 是闭合括号,所以推出栈,stack = []

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

案例 2

再拿 ([)] 举例:

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

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

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

六 总结

返回目录

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

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


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

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

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

扫描上方二维码,关注 jsliang 的公众号(左)和 浪子神剑 的公众号(右),让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于github.com/LiangJunron…上的作品创作。
本许可协议授权之外的使用权限可以从 creativecommons.org/licenses/by… 处获得。

关注下面的标签,发现更多相似文章
评论