用js来实现那些数据结构05(栈02-栈的应用)「建议收藏」

上一篇文章我们一起实现了栈,那么这一篇文章我们一起来用栈解决问题。看看如何用栈来解决进制转换,平衡圆括号以及汉诺塔问题,使我们对栈有更为深入的理解。1、进制转换我们先来看看十进制如何转换成二进制,

大家好,又见面了,我是你们的朋友全栈君。

  上一篇文章我们一起实现了栈,那么这一篇文章我们一起来用栈解决问题。看看如何用栈来解决进制转换平衡圆括号以及汉诺塔问题,使我们对栈有更为深入的理解。

1、进制转换

  我们先来看看十进制如何转换成二进制,十进制整数转换为二进制整数采用”除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。

用js来实现那些数据结构05(栈02-栈的应用)「建议收藏」

  在开始玩汉诺塔游戏之前,我先给大家说一下汉诺塔游戏的规则

    规则一:每次操作只能移动一个圈圈,把它从一个柱子移到另一个柱子上。

    规则二:大圈圈不能架在小圈圈的上面。

  这是游戏的规则,那么换作程序的话,规则是这样的:假设这里有三根相邻的柱子,标号为A,B,C,A柱子上由下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子B上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方,请问至少需要移动多少次?

  我的理解,1、目的是把这个汉诺塔从一个柱子依照由下到上的顺序完整的移动到另一个柱子上,

       2、大圈不能在小圈之下,但是可以隔层放置大小圈,比如八号最大,越往上越小,那么在移动的过程中,5号是可以放在7号上面的。

       3、可以往回放。

  如果还有不清楚规则的地方,可以去这里亲自玩一下这个游戏。

  我们已经对汉诺塔有了简单的了解,那么我们看看如何用栈来实现这个游戏吧:

//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'));

  到这里,我们对栈有了一定的了解,相信大家在今后无论什么情况下遇到“栈”这个词都不会再陌生和懵懂了。那么对栈的学习到这里就基本结束了。下一篇文章会跟大家一起学习一下队列这个数据结构。

  

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124428.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • HDU–2040

    HDU–2040

  • FileUpload1上传控件

    FileUpload1上传控件stringfn=System.IO.Path.GetFileName(FileUpload1.PostedFile.FileName);//获取文件的名字stringfilname=F

  • java分页工具集合「建议收藏」

    java分页工具集合「建议收藏」java分页工具集合说明一、PageHelper(1)pom(2)配置(3)使用正确使用错误使用二、mybatis-plus的分页插件(1)pom(2)配置(3)使用三、自定义工具类(1)创建分页工具类(2)使用说明更新时间:2020/11/617:36,更新完基本内容本文现对目前常见的java分页工具进行一次总结与记录,主要是基于自己的主观来进行总结,本文会持续更新,不断地扩充注意:本文仅为记录学习轨迹,如有侵权,联系删除一、PageHelper这个工具只要是使用过mybatis的人基本都听

  • python怎么调用api_python win32api中文手册

    python怎么调用api_python win32api中文手册#1、获得应用窗口句柄hwnd=win32gui.FindWindow(0,“窗口名字”)#2、通过应用窗口句柄获得窗口DChwndDC=win32gui.GetWindowDC(hwnd)#3、通过hwndDC获得mfcDC(注意主窗口用的是win32gui库,操作位图截图是用win32ui库)mfcDC=win32ui.GreateDCFromHandle(hwnd)#4、创建兼容…

    2022年10月11日
  • 阿里云mqtt服务器_阿里云ecs新手教程

    阿里云mqtt服务器_阿里云ecs新手教程概述本篇主要讲述使用MQTTX软件与阿里云进行连接,上篇文章open62541基于mqtt订阅发布中有有关MQTTX软件的下载以及使用。建立连接这里我们使用MQTTX与阿里云建立连接,阿里云地址:https://iot.console.aliyun.com/lk/summary/new这里我们进行注册以及实名认证后进行登录,登录后界面如下所示:一定要实名认证后才可以使用,使用支付宝实名认证很快也很简单登录后我们就可以开始操作了。添加产品点击公共用例后就会跳转到添加产品界面,如下图所

    2022年10月23日
  • 基于灰色关联度分析法_灰色关联度分析法的优缺点

    基于灰色关联度分析法_灰色关联度分析法的优缺点本文介绍了利用灰色关联度分析方法分析了数据之间的关联度。

    2022年10月24日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号