上一篇文章我们一起实现了栈, 那么这一篇文章我们一起来用栈解决问题. 看看如何用栈来解决进制转换, 平衡圆括号以及汉诺塔问题, 使我们对栈有更为深入的理解.
1, 进制转换
我们先来看看十进制如何转换成二进制 https://baike.baidu.com/item/十进制转二进制/393189?fr=aladdin#2 , 十进制整数转换为二进制整数采用 "除 2 取余, 逆序排列" 法. 具体做法是: 用 2 整除十进制整数, 可以得到一个商和余数; 再用 2 去除商, 又会得到一个商和余数, 如此进行, 直到商为 0 时为止, 然后把先得到的余数作为二进制数的低位有效位, 后得到的余数作为二进制数的高位有效位, 依次排列起来. 简单来说就是拿十进制数去除以二, 如果整除了, 那么余数为 0, 放入栈中, 如果没有整除, 余数就是 1, 放入栈中, 直至相除的结果为 0. 依据所得到的结果, 后得到的余数排列在最前面. 也就是栈顶元素从左到右排列.
我们已经知道了十进制如何转换成二进制, 那么我们看看代码是怎么实现的吧.
- function decimalToBinary(decNumber) {
- // 声明一个 stack 对象
- const remStack = new Stack();
- // 需要转换的数字
- let number = decNumber;
- // 每次相除后所得的余数
- let rem;
- // 转换后的二进制字符串
- let binaryString = '';
- // 当 number 为 0 的时候结束循环
- while (number> 0) {
- // 对余数向下取整, 因为这里不取整的话会出现小数, js 没有浮点或者整形这一说.
- rem = Math.floor(number % 2);
- // 存储当前的余数
- remStack.push(rem);
- // 因为上面对 number 取余只是拿到了最后余数的结果, number 本身并没有除以二, 所以这里除以二是为了保证后面可以再一次取余的结果正确性
- number = Math.floor(number / 2);
- }
- // 这里的意思是如果栈中还有元素, 那么就循环拼接字符串.
- while (!remStack.isEmpty()) {
- binaryString += remStack.pop().toString();
- }
- return binaryString;
- }
- console.log(decimalToBinary(100));//1100100
- console.log(decimalToBinary(1));//1
- console.log(decimalToBinary(2));//10
- console.log(decimalToBinary(111));//1101111
- console.log(decimalToBinary(65));//1000001
那么上面就实现了十进制转换二进制的方法, 那么我想可不可以使它更完善一点, 实现十进制转换成二进制, 八进制, 十六进制等.
- function baseConverter(decNumber, base) {
- const remStack = new Stack();
- // 这是转换的对比字典, 大家知道在十位以后的禁止转换中, 10 用 A 代表, 11 用 B 代表.
- // 所以当我们在转换的时候需要使余数的数字被字母所替换.
- const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
- let number = decNumber;
- let rem;
- let baseString = '';
- // 这里只做 2 到 36 位之间的转换, 因为理论上来讲可以进行任何位数之间的互相转换.
- // 但是在不同位数之间转换的时候会有更为复杂的情况
- if (!(base>= 2 && base <= 36)) {
- return '';
- }
- while (number> 0) {
- rem = Math.floor(number % base);
- remStack.push(rem);
- number = Math.floor(number / base);
- }
- while (!remStack.isEmpty()) {
- baseString += digits[remStack.pop()];
- }
- return baseString;
- }
- console.log(baseConverter(100,16));//64
- console.log(baseConverter(1,16));//1
- console.log(baseConverter(12,8));//14
- console.log(baseConverter(122323123,36));//20TT4J
- console.log(baseConverter(111111111,28));//6CLF9R
- console.log(baseConverter(99,16));//63
我们发现其实对于十进制转换成其它进制, 貌似只是多了一个对照表 digits, 本质上并没有什么区别.
2, 平衡圆括号
- function parenthesesChecker(symbols) {
- const stack = new Stack();
- const opens = '([{';
- const closers = ')]}';
- let balanced = true;
- let index = 0;
- let symbol;
- let top;
- while (index <symbols.length && balanced) {
- // 从 0 开始 (index 的初始值), 给 symbol 赋值
- symbol = symbols.charAt(index);
- // 这里判断 symbol 是否在 opens 中存在, 即 opens.indexOf 的返回值不为负数.
- if (opens.indexOf(symbol)>= 0) {
- // 如果存在, 那么说明是开始符号, 入栈.
- stack.push(symbol);
- // 那么之前判断了是否存在开始符号, 如果不存在的话就不会入栈, 所以 stack 就没有元素, 自然 stack 为空, balanced 返回 false.
- // 因为如果一开始的第一个符号就是尾部符号一定是无法对称平衡的.
- } else if (stack.isEmpty()) {
- balanced = false;
- } else {
- // 获取栈顶元素并移除
- top = stack.pop();
- // 这个 else 其实是当 symbols 中对应的下标没有值得时候, 就说明是 closer 中的值之一.
- // 所以这里的 symbol 其实是 closer, 所以获取最近入栈的值进行比较, 就能判断出是否是平衡的.
- if (!(opens.indexOf(top) === closers.indexOf(symbol))) {
- balanced = false;
- }
- }
- // 继续循环
- index++;
- }
- // 这里, 如果是 balanced 的, 并且 stack 为空, 那么说明我们的所有元素必然是一一对称的.
- // 因为如果不对称是无法完全出栈的
- if (balanced && stack.isEmpty()) {
- return true;
- }
- return false;
- }
- console.log(parenthesesChecker("(()()())"))
- console.log(parenthesesChecker("(({})){["))
- console.log(parenthesesChecker("{}()[]"))
- console.log(parenthesesChecker("{{{}}}}"))
- console.log(parenthesesChecker("[][][]["))
其实这个方法的核心在于, 判断当前下标的参数是头部分还是尾部分, 头部就入栈, 如果是尾部就出栈头部并和当前尾部对比. 正是利用了栈的特性.
3, 汉诺塔
什么是汉诺塔? 我相信很多人小时候都玩过, 有图有真相, 没图不 BB.
在开始玩汉诺塔游戏之前, 我先给大家说一下汉诺塔游戏的规则 https://baike.baidu.com/item/汉诺塔/3468295?fr=aladdin#3_2https://baijiahao.baidu.com/s?id=1565959085480733&wfr=spider&for=pc :
规则一: 每次操作只能移动一个圈圈, 把它从一个柱子移到另一个柱子上.
规则二: 大圈圈不能架在小圈圈的上面.
这是游戏的规则, 那么换作程序的话, 规则是这样的: 假设这里有三根相邻的柱子, 标号为 A,B,C,A 柱子上由下到上按金字塔状叠放着 n 个不同大小的圆盘, 要把所有盘子一个一个移动到柱子 B 上, 并且每次移动同一根柱子上都不能出现大盘子在小盘子上方, 请问至少需要移动多少次?
我的理解, 1, 目的是把这个汉诺塔从一个柱子依照由下到上的顺序完整的移动到另一个柱子上,
2, 大圈不能在小圈之下, 但是可以隔层放置大小圈, 比如八号最大, 越往上越小, 那么在移动的过程中, 5 号是可以放在 7 号上面的.
3, 可以往回放.
如果还有不清楚规则的地方, 可以去这里 http://www.4399.com/flash/109504_1.htm 亲自玩一下这个游戏.
我们已经对汉诺塔有了简单的了解, 那么我们看看如何用栈来实现这个游戏吧:
- //plates: 盘子数量, source 源柱子, helper 暂存柱子, dest 目标柱子, sourceName 源柱子名称, helperName 暂存柱子名称, destName 目标柱子名称, moves 步数 (若不传值则默认为一个数组)
- function towerOfHanoi(plates, source, helper, dest, sourceName, helperName, destName, moves = []) {
- console.log(moves.length)
- // 如果盘子的数字不大于 0 , 那么直接返回 moves, 终止递归的条件.
- if (plates <= 0) return moves;
- if (plates === 1) {
- dest.push(source.pop());
- const move = {};
- move[sourceName] = source.toString();
- move[helperName] = helper.toString();
- move[destName] = dest.toString();
- moves.push(move);
- } else {
- // 递归调用自身. 并且将盘子的数量减少一个, 这里交换了 dest 和 helper 的位置, 是为了 dest.push 中存入的栈是 helper 栈, 也就是说是为了存入对应的柱子.
- towerOfHanoi(plates - 1, source, dest, helper, sourceName, destName, helperName, moves);
- // 从源柱子拿出最顶层的一个放入目标柱子 (如果 dest 和 helper 互换了位置, 那么其实这里的 dest 实际上代表的是 helper)
- dest.push(source.pop());
- // 声明常量, 用来存储当前各个柱子的盘子栈况
- const move = {};
- move[sourceName] = source.toString();
- move[helperName] = helper.toString();
- move[destName] = dest.toString();
- // 存入 moves
- moves.push(move);
- towerOfHanoi(plates - 1, helper, source, dest, helperName, sourceName, destName, moves);
- }
- return moves;
- }
- function hanoiStack(plates) {
- // 创建每一个柱子的栈对象, source 是最开始拥有所有圈圈的柱子, dest 是目标柱子, helper 是中间的暂存柱子
- const source = new Stack();
- const dest = new Stack();
- const helper = new Stack();
- // 倒序循环把每一个圈圈序号放入 source 栈
- for (let i = plates; i> 0; i--) {
- source.push(i);
- }
- // 通过 return 调用 towerOfHanoi 计算方法.
- return towerOfHanoi(plates, source, helper, dest, 'source', 'helper', 'dest');
- }
- // 这个方法是计算在汉诺塔的层数为 plates 的时候, 每一个是从哪个柱子拿到哪个柱子的
- function hanoi(plates, source, helper, dest, moves = []) {
- if (plates <= 0) return moves;
- if (plates === 1) {
- moves.push([source, dest]);
- } else {
- hanoi(plates - 1, source, dest, helper, moves);
- moves.push([source, dest]);
- hanoi(plates - 1, helper, source, dest, moves);
- }
- return moves;
- }
- console.log(hanoiStack(2))
- console.log(hanoi(8, 'source', 'helper', 'dest'));
到这里, 我们对栈有了一定的了解, 相信大家在今后无论什么情况下遇到 "栈" 这个词都不会再陌生和懵懂了. 那么对栈的学习到这里就基本结束了. 下一篇文章会跟大家一起学习一下队列这个数据结构.
最后, 由于本人水平有限, 能力与大神仍相差甚远, 若有错误或不明之处, 还望大家不吝赐教指正. 非常感谢!
来源: https://www.cnblogs.com/zaking/p/8837056.html