«

JS表示Stack类怎么用栈实现任意进制转换

时间:2024-5-21 09:05     作者:韩俊     分类: Javascript


这篇文章主要讲解了“JS表示Stack类怎么用栈实现任意进制转换”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“JS表示Stack类怎么用栈实现任意进制转换”吧!

基本概念

夯下数据结构和算法基础,JS 里没有栈、队列、链表巴拉巴拉明显的结构,只能用类去伪造,不然做算法题真的费劲。
先造最简单的栈类吧,这边底层使用数组,当然有空的话,你也可以试试对象。

    栈是一种遵从后进先出(LIFO)原则的有序集合

    新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底(类似,叠盘子)

    在栈里,新元素都靠近栈顶,旧元素都靠近栈底。

基本方法

    push(i) 添加一个(或几个)新元素到栈顶。

    pop() 移除栈顶的元素,同时返回被移除的元素。

    peek() 返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。

    isEmpty() 如果栈里没有任何元素就返回 true,否则返回 false。

    clear() 移除栈里的所有元素。

    size() 返回栈里的元素个数。这个方法和数组的 length 属性很类似。

类实现

class Stack {
  stack: any[];
  constructor() {
    this.stack = [];
  }
  size() {
    return this.stack.length;
  }
  peek() {
    return this.stack[this.stack.length - 1];
  }
  push(value: any) {
    this.stack.push(value);
  }
  pop() {
    return this.stack.pop();
  }
  isEmpty() {
    return this.size() === 0;
  }
  clear() {
    this.stack = [];
  }
}

可以头上顶个注释,就容易调用方法了

/**
 * 栈类
 * @class Stack
 * @description 栈是一种遵从后进先出(LIFO)原则的有序集合。
 * 新添加或待删除的元素都保存在栈的同一端,称作栈顶,另一端就叫栈底。
 * 在栈里,新元素都靠近栈顶,旧元素都靠近栈底。
 * @property stack 栈内部存储的数组
 *
 * @method push(element(s)) 添加一个(或几个)新元素到栈顶。
 * @method pop() 移除栈顶的元素,同时返回被移除的元素。
 * @method peek() 返回栈顶的元素,不对栈做任何修改(该方法不会移除栈顶的元素,仅仅返回它)。
 * @method isEmpty() 如果栈里没有任何元素就返回 true,否则返回 false。
 * @method clear() 移除栈里的所有元素。
 * @method size() 返回栈里的元素个数。这个方法和数组的 length 属性很类似。
 *
 * @example
 * const s = new Stack()
 * s.push(1)
 * s.push(2)
 * s.push(3)
 * s.pop() // 3
 * s.pop() // 2
 * s.pop() // 1
 * s.pop() // undefined
 * s.push(1)
 * s.push(2)
 * s.push(3)
 * s.peek() // 3
 * s.size() // 3
 * s.isEmpty() // false
 * s.clear()
 * s.isEmpty() // true
 * s.size() // 0
 *
 */

应用场景

栈的应用场景:浏览器的历史记录、存储访问过的任务、撤销的操作等等。

练习 1:十进制数字转化为二进制

十进制数字转化为二进制的逻辑是:

关键逻辑:用十进制数除以 2,得到的余数存入栈中,得到的商(迭代)继续除以 2, 得到的余数再继续存入栈中(循环),直到商为 0 为止(终止条件)。

function toBinary(decNumber: number) {
  const s = new Stack();
  // 迭代指针,每次得到的商,初始是原始值
  let p = decNumber;
  // 商不为0 就一直循环
  while (p !== 0) {
    // 余数进栈
    s.push(p % 2);
    // 迭代
    p = Math.floor(p / 2);
  }
  let result = '';
  // 数字出栈,拼接,直至栈为空
  while (!s.isEmpty()) {
    result += s.pop();
  }
  return result;
}

加上注释的话

/**
 * 十进制转二进制
 * 1. 用十进制数除以 2,得到的余数存入栈中,得到的商继续除以2 得到的余数继续存入栈中,直到商为 0 为止。
 * @param {number} decNumber 十进制数
 * @returns {string} 二进制数
 * @example
 * toBinary(2) // '10'
 * toBinary(3) // '11'
 * toBinary(4) // '100'
 * toBinary(5) // '101'
 */

练习 2:十进制数字转化为任意进制

转化逻辑和上面的二进制大同小异,但这里有个限制,任意进制的范围是 2-36,然后超过 10 就是

ABCD....
,注意下这里就行

function toBaseConverter(decNumber: number, base: number) {
  // 范围限定
  if (base < 2 || base > 36) throw new Error('base must between 2 and 36');
  const s = new Stack();
  let p = decNumber;
  // 加了这行,超过10的表示
  const baseStr = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  while (p !== 0) {
    // s.push(p % 2) 换下,因为有字母,所以这样写法,没有字母的话p % base就够用
    s.push(baseStr[p % base]);
    // p = Math.floor(p / 2) 的2换成base
    p = Math.floor(p / base);
  }
  let result = '';
  while (!s.isEmpty()) {
    result += s.pop();
  }
  return result;
}

加上注释的话

/**
 * 十进制转任意进制
 * @param {number} decNumber 十进制数
 * @param {number} base 进制
 * @returns {string} 任意进制数
 * @example
 * toBaseConverter(20,5) // '40'
 * toBaseConverter(20,2) // '10100'
 * toBaseConverter(20,8) // '24'
 * toBaseConverter(20,16) // '14'
 * toBaseConverter(20,36) // 'E'
 * toBaseConverter(20,37) // Error: base must between 2 and 36
 */

标签: javascript

热门推荐