JS栈类实现与任意进制转换算法详解

基本概念

夯实数据结构和算法基础，JavaScript 原生并未提供栈、队列、链表等明显的数据结构，因此需要利用类来模拟实现，否则进行算法题练习会非常困难。首先构建最基础的栈类，底层数据结构选用数组，后续若有兴趣也可尝试使用对象实现。

栈是一种遵循后进先出（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数据结构与算法》（希望我能看完）

以上就是JS表示Stack类练习用栈实现任意进制转换的详细内容，更多关于JS表示Stack类进制转换的资料请关注本站其它相关文章！

JavaScript 实现 Stack 栈类及任意进制转换算法

基本概念

基本方法

类实现

应用场景

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

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

实用工具推荐