JS表示Stack类练习用栈实现任意进制转换

JS表示Stack类进制转换 JS表示Stack类 2023-05-17 17:05:57 914人浏览泡泡鱼

摘要

目录基本概念基本方法类实现应用场景练习 1：十进制数字转化为二进制练习 2：十进制数字转化为任意进制基本概念夯下数据结构和算法基础，js 里没有栈、队列、链表巴拉巴拉明显的结构，只

基本概念

夯下数据结构和算法基础，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 = [];
  }
}

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

应用场景

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

练习 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;
}

加上注释的话

练习 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;
}

加上注释的话

引用